首页 > 代码库 > Binary Tree & Divide Conquer 完整笔记l
Binary Tree & Divide Conquer 完整笔记l
1. 前序遍历
1.1 前序遍历的非递归的方式
利用stack
while (!stack.isEmpty()) {
pop作为根节点；
根节点加入result list；
把右边节点加入到stack；
把左边节点加入到stack；
}
1 public class Solution { 2 public List<Integer> preorderTraversal(TreeNode root) { 3 Stack<TreeNode> stack = new Stack<TreeNode>(); 4 List<Integer> preorder = new ArrayList<Integer>(); 5 6 if (root == null) { 7 return preorder; 8 } 9 stack.push(root);10 11 while(!stack.isEmpty()) {12 TreeNode current = stack.pop();13 preorder.add(current.val);14 if (current.right != null) {15 stack.push(current.right);16 }17 if (current.left != null) {18 stack.push(current.left);19 }20 }21 return preorder;22 }23 }
1.2 前序遍历的Traverse 递归方式
traverse 到某个节点，把当前的root加入到result list里面， 然后去遍历它的左右儿子。
traverse方式把一个result储存结果的list在遍历的同时传递，一旦有新的点，就加入到result里面。
递归的function不用返回任何值，而是在function里面对传入的值进行更新处理。
1 public class Solution { 2 public ArrayList<Integer> preorderTraversal(TreeNode root) { 3 ArrayList<Integer> result = new ArrayList<Integer>(); 4 traverse(root, result); 5 return result; 6 } 7 // 把root为跟的preorder加入result里面 8 private void traverse(TreeNode root, ArrayList<Integer> result) { 9 if (root == null) {10 return;11 }12 13 result.add(root.val);14 traverse(root.left, result);15 traverse(root.right, result);16 }17 }
以上是traverse二叉树的代码
附上traverse图的version
1 public class Solution { 2 public List<Integer> preorderTraversal(Node root) { 3 List<Integer> result = new ArrayList<Integer>(); 4 if (root == null) { 5 return result; 6 } 7 traverse(result, root); 8 return result; 9 }10 private void traverse(List<Integer> result, Node root) {11 if (root == null) {12 return;13 } 14 //针对于有环的图 还需要visitied queue来判断是否已经visited15 result.add(root.val);16 Queue<Node> queue = new Queue<Node>();17 current = root.child; //假设child存在链表里18 while (current != null) {19 queue.add(current);20 current = current.next;21 }22 23 24 for (Node current : stack) {25 traverse(result, current);26 27 }28 }29 }
1.3 前序遍历的 divide and conquer方式
//todo
1 public class Solution { 2 private static List<Integer> result; 3 public List<Integer> preorderTraversal(TreeNode root) { 4 result = new ArrayList<Integer>(); 5 if (root == null) { 6 return result; 7 } 8 helper (root); 9 return result;10 }11 private void helper(TreeNode root) {12 if (root == null) {13 return;14 }15 result.add(root.val);16 helper(root.left);17 helper(root.right);18 }19 }
Binary Tree & Divide Conquer 完整笔记l
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。