Binary Tree Traversal

-

Traversal (#66, #67, #68)

Recursion

Recursion 模板

public class Solution {
    public List<Integer> recursionTeraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        recursion(root, result);
        return result;
    }

    private void recursion(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        recursion(root.left, result);
        recursion(root.right, result);
    }
}

1. Preorder (中左右)

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root, result);
        return result;
    }
 
    private void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

2. Inorder (左中右)

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
    
    private void inorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}

3. Postorder (左右中)

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
    
    private void postorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        postorder(root.left, result);
        postorder(root.right, result);
        result.add(root.val);
    }
}

Non-Recursion

Non-Recursion 模板

public class Solution {
    public List<Integer> nonRecursionTeraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> result = new ArrayList<Integer>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                result.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        Collections.reverse(result);
        return result;
    }
}

1. Preorder (中左右)

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> result = new ArrayList<Integer>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                result.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return result;
    }
}

2. Inorder (左中右)

public class Solution {
    public List<Integer>  inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer>  result = new ArrayList<Integer>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        return result;
    }
}

3. Postorder (左右中)

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> result = new ArrayList<Integer>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                result.add(root.val);
                stack.push(root);
                root = root.right;
            }
            root = stack.pop();
            root = root.left;
        }
        Collections.reverse(result);
        return result;
    }
}

Non-Recursion-2

Non-Recursion 模板 (例如：左中右是我们想看到的，即pop顺序，那相对的push顺序就应该是中左右，对于加入到result，划重点：先加入到result中，再push/pop)

public class Solution {
    public List<Integer> nonRecursionTeraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        TreeNode dummy = new TreeNode(0);
        dummy.right = root;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(dummy);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                node = node.right;
                while (node != null) {
                    result.add(node.val);
                    stack.push(node);
                    node = node.left;
                }
            }
            if (!stack.isEmpty()) {
                result.add(stack.peek().val);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

1. Preorder (中左右)

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
       
        TreeNode dummy = new TreeNode(0);
        dummy.right = root;
       
        Stack<TreeNode> stack = new Stack<>();
        stack.push(dummy);
       
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                node = node.right;
                while (node != null) {
                    result.add(node.val);
                    stack.push(node);
                    node = node.left;
                }
            }
        }
        return result;
    }
}

2. Inorder (左中右)

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
       
        TreeNode dummy = new TreeNode(0);
        dummy.right = root;
       
        Stack<TreeNode> stack = new Stack<>();
        stack.push(dummy);
       
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                node = node.right;
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
            }
            if (!stack.isEmpty()) {
                result.add(stack.peek().val);
            }
        }
        return result;
    }
}

3. Postorder (左右中)

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
       
        TreeNode dummy = new TreeNode(0);
        dummy.left = root;
       
        Stack<TreeNode> stack = new Stack<>();
        stack.push(dummy);
       
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                node = node.left;
                while (node != null) {
                    result.add(node.val);
                    stack.push(node);
                    node = node.right;
                }
            }
        }
        Collections.reverse(result);
        return result;
    }
}

 Divide Conquer

Divide Conquer 模板

public class Solution {
    public List<Integer> divideConquerTeraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null){
            return result;
        }

        List<Integer> left = divideConquerTeraversal(root.left);
        List<Integer> right = divideConquerTeraversal(root.right);

        result.add(root.val);
        result.addAll(left);
        result.addAll(right);

        return result;
    }
}

1. Preorder (中左右)

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null){
            return result;
        }

        List<Integer> left = preorderTraversal(root.left);
        List<Integer> right = preorderTraversal(root.right);
   
        result.add(root.val);
        result.addAll(left);
        result.addAll(right);

        return result;
    }
}

2. Inorder (左中右)

public class Solution {
    public List<Integer>  inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null){
            return result;
        }

        List<Integer> left = inorderTraversal(root.left);
        List<Integer> right = inorderTraversal(root.right);

        result.addAll(left);
        result.add(root.val);
        result.addAll(right);

        return result;
    }
}

3. Postorder (左右中)

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null){
            return result;
        }
   
        List<Integer> left = postorderTraversal(root.left);
        List<Integer> right = postorderTraversal(root.right);
   
        result.addAll(left);
        result.addAll(right);
        result.add(root.val);

        return result;
    }
}

Comments

Post a Comment

Popular posts from this blog

Union Find 模板

-
Union Find Union Find Union Find 动态的计算联通块问题 结构 global variables constructor() find(int x) union(int a, int b) 模板 (Map) global variables private Map<Integer, Integer> f; constructor() UnionFind(int n) { this.f = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { f.put(i, i); } } find(int x) int find(int x) { int root = x; // 找到“根” while (f.get(root) != root) { root = f.get(root); } // 拆“整”为“零”，把每个元素直接接到“根”上 while (root != x) { int nx = f.get(x); f.put(x, root); x = nx; } return root; } union(int a, int b) void union(int a, int b) { int rA = find(a); int rB = find(b); if (rA != rB) { f.put(rB, rA); } } 例题 Friend Circles 根据模板添加额外的全局变量，比如此题需要count，在每次合并的时候 count-- ，在初始化的时候或者写一个 setter 和 getter 去给 count 赋值和取值 public class Solution { class UnionFind { private int count; private Map...
Read more

Tree的经典题

-
Tree的经典题 Tree的经典题 找第k小 Kth Smallest Element in a BST 在树上就不需要使用Heap了，因为inorder traversal本身就是一个从小到大的序列，这里我们有几种方法 1. Recursive traversal 创建全局变量，记录traverse到哪儿了，当走到k的时候把值赋给result即可 时间复杂度 O(n) public class Solution { //设置全局变量 private int count = 0; private int result = 0; public int kthSmallest(TreeNode root, int k) { traversal(root, k); return result; } private void traversal(TreeNode root, int k) { if (root == null) { return; } traversal(root.left, k); //如果count等于k的时候才把结果赋给result //注意count从0开始，所以count先++之后再判断 count++; if (count == k) { result = root.val; } traversal(root.right, k); } } 2. Quick Select on Tree 首先要traverse计算每个点到它的时候子树总共有多少个点，然后用quick select，如果大于k，直接去左边找，如果小于k，判断当左边的个数加1正好等于k，那么这个k就落在root上，如果加1之后还小于k那么就要去向右边找了，因为此时左边没有第k个点。 时间复杂度 O(n) 最好最坏都是 public class Solution { public int kthSmal...
Read more

Tree DFS

-
Tree DFS Tree DFS Tree上的DFS分为两种（Divide Conquer + Traversal和纯Divide Conquer） 建立当前/用全局变量（根据不同的方式） root 为 空 （ 返回 什么/ 更新 指针） 左 节点和 右 节点 都 为 空 ，用 root 构建 当前 解（ 返回 什么/ 更新 指针） 左 节点和 右 节点 不 为 空 ，用 左右 构建 当前 解 返回 当前 /选择 左 ， 右 ， 中 Divide Conquer + Traversal 不同 一般 没有 全局变量， 创建当前 变量作为当前最终解 通过 左 节点的最终解和 右 节点的最终解， 计算 并更新 当前 变量 判断 左 节点的最终解， 右 节点的最终解， 当前 变量，在三个解中 选择 一个 作为当前层的最终解 返回 更新传入的参数指针 （ 有时会单独建立 class Result 类 ） 流程 建立 当前 变量（不一定第一步） root 为 空 （ 返回 什么） left 节点和 right 节点 都 为 空 ，用 root 构建 当前 解（ 返回 什么/ 更新 指针） left 节点和 right 节点 不 为 空 ，用 左右 解 leftResult , rightResult 计算 当前 解 选择 符合的解 比较 （ leftResult ， rightResult ， result ） + 选出 合适的解 直接使用 ：当前解 使用 选中的解 返回 更新 传入的指针 例题（Minimum Subtree） public class Solution { class Result { TreeNode minSubtree; int minSum; int sum; Result(TreeNode minSubtree, int minSum, int sum) { this.minSubtree = minSubtree; this...
Read more