[Leetcode][Tree--1]树相关题目汇总/分析/总结

2019-06-19 本文已影响0人奔跑的程序媛A

Binary Tree
(1) Traversal
(2) Path
- 124 Binary Tree Maximum Path Sum
- 257 Binary Tree Paths
- 112 Path Sum
- 113 Path Sum II
- 437 Path Sum III
(3) Verify/Modify
- 110 Balanced Binary Tree
- 226 Invert Binary Tree
- 199 Binary Tree Right Side View
- 114 Flatten Binary Tree to Linked List
- 331 Verify Preorder Serialization of a Binary Tree
(4) Depth / Width
- 111 Minimum Depth of Binary Tree
- 104 Maximum Depth of Binary Tree
- 662 Maximum Width of Binary Tree
(5) Sum
- 404 Sum of Left Leaves
- 129 Sum Root to Leaf Numbers
- 563 Binary Tree Tilt

[Binary Tree][Traversal]

#144 Binary Tree Preorder Traversal

Preorder基础--前序遍历：根左右

Sol1 Recursive

    List<Integer> res;
    public List<Integer> preorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        help(root);
        return res;
    }
    public void help(TreeNode root){
        if(root == null) return;
        res.add(root.val);
        help(root.left);
        help(root.right);
    }

Sol2 Iterating

public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> s = new Stack<>();
       while(!s.isEmpty() || root != null){
           while(root != null){
               res.add(root.val);
               s.push(root);
               root = root.left;
           }
           root = s.pop().right;
       }
       return res;
   }

#94 Binary Tree Inorder Traversal

Inorder基础--中序遍历：左根右

Sol Recursive
Time O(n) : T(n) = 2 *T(n/2)+1

    List<Integer> res;
    public List<Integer> inorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        help(root);
        return res;
    }
    public void help(TreeNode root){
        if(root == null) return;
        help(root.left);
        res.add(root.val);
        help(root.right);
    }

Sol2 Iterating
Stack
Time O(n)
Space O(n)

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        while(!s.isEmpty() || root != null){
            while(root != null){
                s.push(root);
                root = root.left;
            }
            root = s.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

#145 Binary Tree Postorder Traversal

Postorder基础--后序遍历：左右根

Sol1 Recursive

    List<Integer> res;
    public List<Integer> postorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        help(root);
        return res;
    }
    public void help(TreeNode root){
        if(root == null) return;
        help(root.left);
        help(root.right);
        res.add(root.val);
    }

Sol2 Iterating
LinkedList + Stack

    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                res.addFirst(cur.val);
                stack.push(cur);
                cur = cur.right;

            } else {
                cur = stack.pop();
                cur = cur.left;
            }
        }
        return res;
    }

#102 Binary Tree Level Order Traversal

Sol1 Recursive

    List<List<Integer>> res;
    public List<List<Integer>> levelOrder(TreeNode root) {
        res = new ArrayList<>();
        help(root, 1);
        return res;
    }
    public void help(TreeNode root, int level){
        if(root == null) return;
        if(res.size() < level) res.add(new ArrayList<>());
        res.get(level-1).add(root.val);
        help(root.left, level+1);
        help(root.right, level+1);
    }

Sol2 Iterating
Queue

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode cur = root;
        q.add(cur);
        while(!q.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int n = q.size();
            for(int i = 0; i < n; i++){
                TreeNode l = q.remove();
                tmp.add(l.val);
                if(l.left != null) q.add(l.left);
                if(l.right != null) q.add(l.right);
            }
            res.add(tmp);
        }
        return res;
    }

#107 Binary Tree Level Order Traversal II

Sol1 Recursive
Collections.reverse(res);

    List<List<Integer>> res;
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        res = new ArrayList<>();
        help(root, 1);
        Collections.reverse(res);
        return res;
    }
    public void help(TreeNode root, int level){
        if(root == null) return;
        if(res.size() < level) res.add(new ArrayList<>());
        res.get(level-1).add(root.val);
        help(root.left, level+1);
        help(root.right, level+1);
    }

Sol2 Iterating
res.add(0, tmp);

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int n = q.size();
            for(int i = 0; i < n; i++){
                root = q.remove();
                tmp.add(root.val);
                if(root.left!=null)
                    q.offer(root.left);
                if(root.right!=null)
                    q.offer(root.right);
            }
            res.add(0, tmp);
        }
        return res;
    }

#103 Binary Tree Zigzag Level Order Traversal

Sol1 Recursive

   List<List<Integer>> res;
   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
       res = new ArrayList<>();
       help(root, 1);
       boolean reverse = false;
       for(List<Integer> tmp : res){
           if(reverse) Collections.reverse(tmp);
           reverse = !reverse;
       }
       return res;
   }
   public void help(TreeNode root, int level){
       if(root == null) return;
       if(res.size() < level) res.add(new ArrayList<>());
       res.get(level-1).add(root.val);
       help(root.left, level+1);
       help(root.right, level+1);
   }

Sol2 Iterating
Queue

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean reverse = false;
        while(!q.isEmpty()){
            int n = q.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < n; i++){
                TreeNode l = q.remove();
                tmp.add(l.val);
                if(l.left!=null) q.add(l.left);
                if(l.right != null) q.add(l.right);
            }
            if(reverse) Collections.reverse(tmp);
            res.add(tmp);
            reverse = !reverse;
        }
        return res;
    }

#105 Construct Binary Tree from Preorder and Inorder Traversal

Sol1 Recursive

int index = 0;
    Map<Integer, Integer> m;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0) return null;
        m = new HashMap<>();
        for(int i = 0; i < inorder.length; i++) m.put(inorder[i], i);
        return build(preorder, inorder, 0, inorder.length-1);
    }
    
    public TreeNode build(int[] pre, int[] in, int i, int j) {
        if(i>j) return null;
        int pivot = m.get(pre[index]);
        TreeNode n = new TreeNode(pre[index]);
        index++;
        n.left = build(pre, in, i, pivot-1);
        n.right = build(pre, in, pivot+1, j);
        return n;
    }

Sol2 Iterating

public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0) return null;
        Map<Integer, Integer> m = new HashMap<>();
        for(int i = 0; i < inorder.length; i++) m.put(inorder[i], i);
        Stack<TreeNode> s = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        s.add(root);
        for(int i = 1; i < preorder.length; i++){
            Integer value = preorder[i];
            TreeNode tmp = new TreeNode(value);
            if(m.get(value) < m.get(s.peek().val)) s.peek().left = tmp;
            else {
                TreeNode t = null;
                while(!s.isEmpty() && m.get(value) > m.get(s.peek().val)){
                    t = s.pop();
                }
                t.right = tmp;
            }
            s.add(tmp);
        }
        return root;
    }

#106 Construct Binary Tree from Inorder and Postorder Traversal

Sol1 Recursive

    Map<Integer, Integer> m;
    // int index;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = postorder.length;
        if(n == 0) return null;
        m = new HashMap<>();
        for(int i = 0; i < n; i++) m.put(inorder[i], i);
        // index = n-1;
        return build(n-1, postorder, 0, n-1);
    }
    public TreeNode build(int index, int[] postorder, int l, int r){
        if(l > r || index < 0) return null;
        int pivot = m.get(postorder[index]);
        TreeNode n = new TreeNode(postorder[index]);
        // index--;
        n.left = build(index - r + pivot - 1, postorder, l, pivot-1);
        n.right = build(--index, postorder, pivot+1, r);
        return n;
    }

Sol2 Iterating

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = postorder.length;
        if(n == 0) return null;
        Map<Integer, Integer> m = new HashMap<>();
        for(int i = 0; i < n; i++) m.put(inorder[i], i);
        Stack<TreeNode> s = new Stack<>();
        TreeNode root = new TreeNode(postorder[n-1]);
        s.add(root);
        for(int i = n-2; i>= 0; i--){
            Integer value = postorder[i];
            TreeNode tmp = new TreeNode(value);
            if(m.get(value) > m.get(s.peek().val)) s.peek().right = tmp;
            else{
                TreeNode parent = null;
                while(!s.isEmpty() && (m.get(value) < m.get(s.peek().val))){
                    parent = s.pop();
                }
                parent.left = tmp;
            }
            s.add(tmp);
        }
        return root;
    }

[Binary Tree][Path]

#124 Binary Tree Maximum Path Sum

Sol Recursive

    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        help(root);
        return res;
    }
    public Integer help(TreeNode root) {
        if(root == null) return null;
        Integer left = help(root.left);
        Integer right = help(root.right);
        int tmp = root.val;
        if(left != null){
            tmp = Math.max(tmp, root.val + left);
        }
        if(right != null){
            tmp = Math.max(tmp, root.val + right);
        }
        if(left != null && right != null){
            tmp = Math.max(tmp, root.val + Math.max(right, left));
        }
        if(left != null || right != null) {
            if(left == null) res = Math.max(res, right);
            else if(right == null) res = Math.max(res, left);
            else res = Math.max(res, right + left + root.val);
        }
        res = Math.max(res, tmp);
        return tmp;
    }

#257 Binary Tree Paths

Sol1 HashMap + BFS + Stack
Use HashMap to store the path of current treenode.

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root == null) return res;
        String s = "";
        Stack<TreeNode> stack = new Stack<>();
        Map<TreeNode, String> m = new HashMap<>();
        m.put(root, root.val+"");
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur.left == null && cur.right==null) res.add(m.get(cur));
            if(cur.right != null){
                stack.add(cur.right);
                m.put(cur.right, m.get(cur) + "->" + cur.right.val);
            }
            if(cur.left != null){
                stack.add(cur.left);
                m.put(cur.left, m.get(cur) + "->" + cur.left.val);
            }
        }
        return res;
    }

Sol2 Recursive

    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }else{
            List<String> left = binaryTreePaths(root.left);
            List<String> right = binaryTreePaths(root.right);
            ArrayList<String> result = new ArrayList<>();
            for (String l : left) {
                result.add(root.val + "->" + l);
            }
            for (String r : right) {
                result.add(root.val + "->" + r);
            }
            if (result.isEmpty()) {
                result.add(root.val + "");
            }
            return result;
        }
    }

List<String> res;
    public List<String> binaryTreePaths(TreeNode root) {
        res = new ArrayList<>();
        help(root, "");
        return res;
    }
    public void help(TreeNode root, String s){
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null){
            s = s + root.val;
            res.add(s);
            return;
        }
        String tmp = s;
        s = s + root.val + "->";
        help(root.left, s);
        help(root.right, s);
    }

#112 Path Sum

Sol Recursive

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        if(root.right==null && root.left==null) return root.val == sum;
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }

#113 Path Sum II

Sol Recursive
Pre Order

    List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new ArrayList<>();
        help(root, new ArrayList<>(), sum);
        return res;
    }
    public void help(TreeNode root, List<Integer> tmp, int sum){
        if(root == null) return;
        tmp.add(root.val);
        if(root.left == null && root.right == null){
            if(sum == root.val) res.add(new ArrayList<>(tmp));
        }
        help(root.left, tmp, sum - root.val);
        help(root.right, tmp, sum - root.val);
        tmp.remove(tmp.size()-1);
    }

#437 Path Sum III

Sol Recursive
prefix travers + Backtracking

    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return help(root, map, sum, 0);
    }
    public int help(TreeNode root, Map<Integer, Integer> map, int sum, int cur){
        if(root == null) return 0;
        cur += root.val;
        int res = map.getOrDefault(cur - sum, 0);
        map.put(cur, map.getOrDefault(cur, 0) + 1);
        res += help(root.left, map, sum, cur) + help(root.right, map, sum, cur);
        map.put(cur, map.get(cur) - 1);
        return res;
    }

[Binary Tree][Verify/Modify]

#110 Balanced Binary Tree

Sol Recursive

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int depth(TreeNode root){
        if(root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

#226 Invert Binary Tree

Sol1 Recursive

    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        root.left = right;
        root.right = left;

        return root;
    }

Sol2 Iterative

    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode cur = q.remove();
            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;
            if(cur.left!=null) q.add(cur.left);
            if(cur.right!=null) q.add(cur.right);
        }
        return root;
    }

#199 Binary Tree Right Side View

Sol1 Iterative
BFS

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int n = q.size();
            while(n > 1){
                root = q.remove();
                if(root.left != null) q.add(root.left);
                if(root.right != null) q.add(root.right);
                n--;
            }
            root = q.remove();
            if(root.left != null) q.add(root.left);
            if(root.right != null) q.add(root.right);
            res.add(root.val);
        }
        return res;
    }

Sol2 Recursive
Level order -- BFS

    List<Integer> res;
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null) return new ArrayList<>();
        res = new ArrayList<>();
        help(root, 0);
        return res;
    }
    public void help(TreeNode root, int level){
        if(root == null) return;
        if(res.size() <= level) res.add(root.val);
        help(root.right, level+1);
        help(root.left, level+1);
    }

#114 Flatten Binary Tree to Linked List

Sol1 Recursive

    public void flatten(TreeNode root) {
        if(root == null) return;
        TreeNode tmp = root.right;
        TreeNode left = root.left;
        flatten(left);
        root.right = left;
        root.left = null;
        TreeNode cur = root;
        while(cur.right != null){
            cur = cur.right;
        }
        flatten(tmp);
        cur.right = tmp;
    }

#331 Verify Preorder Serialization of a Binary Tree

Sol1 Stack
每个node一定会有两个node，遍历Sring，如果是‘#’则push进stack，如果不是，则pop()两个node

    public boolean isValidSerialization(String preorder) {
        Stack<String> s = new Stack<>();
        String[] str = preorder.split(",");
        for(int i = str.length-1; i>= 0; i--){
            if(!str[i].equals("#")){
                if(s.size() < 2) return false;
                s.pop();
                s.pop();
            }
            s.add(str[i]);
        }
        return s.size() == 1;
    }

[Binary Tree][Depth]

#111 Minimum Depth of Binary Tree

Sol 1 Recursive

    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if (root.left == null && root.right == null) return  1;
        if (root.left == null) return minDepth(root.right)+1;
        if (root.right == null) return minDepth(root.left)+1;
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }

Sol2 Iterative

    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int result = 1;
        while(!q.isEmpty()){
            int n = q.size();
            for(int i = 0; i < n; i++){
                root = q.poll();
                if(root.right == null && root.left == null) return result;
                if(root.left!=null) q.offer(root.left);
                if(root.right!=null) q.offer(root.right);
            }
            result++;
        }
        return result;
    }

#104 Maximum Depth of Binary Tree

Sol1 Recursive

    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        if(root.left ==null) return maxDepth(root.right) + 1;
        if(root.right == null) return maxDepth(root.left) + 1;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

Iterative

    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int result = 0;
        int depth = 1;
        while(!q.isEmpty()){
            int n = q.size();
            for(int i = 0; i < n; i++){
                root = q.remove();
                if(root.left!=null) q.offer(root.left);
                if(root.right!=null) q.offer(root.right);
                if(root.left == null && root.right == null) result = Math.max(result, depth);
            }
            // result++;
            depth++;
        }
        return result;
    }

#662 Maximum Width of Binary Tree

Sol1 BFS

public class Pack {
    TreeNode node;
    int pos;
    Pack(TreeNode node, int pos) {
        this.node = node;
        this.pos = pos;
    }
}
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        Queue<Pack> q = new LinkedList<>();
        q.offer(new Pack(root, 0));
        int width = 1;
        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        while(!q.isEmpty()){
            int n = q.size();
            for(int i = 0; i < n; i++){
                Pack tmp = q.poll();
                if(tmp.node.left!=null) {
                    q.offer(new Pack(tmp.node.left, tmp.pos * 2));
                    left = Math.min(left, tmp.pos * 2);
                    right = Math.max(right, tmp.pos * 2);
                }
                if(tmp.node.right!=null) {
                    q.offer(new Pack(tmp.node.right, tmp.pos * 2 + 1));
                    right = Math.max(right, tmp.pos * 2 + 1);
                    left = Math.min(left, tmp.pos * 2 + 1);
                }
            }
            int tmp = 0;
            if(left == Integer.MAX_VALUE || right == Integer.MIN_VALUE) tmp = 1;
            else tmp = right - left + 1;
            width = Math.max(width, tmp);
            left = Integer.MAX_VALUE;
            right = Integer.MIN_VALUE;
        }
        return width;
    }
}

[Binary Tree][Sum]

#404 Sum of Left Leaves

Sol1 Recursive

    int res = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        help(root, false);
        return res;
    }
    public void help(TreeNode root, boolean left){
        if(root == null) return;
        if(root.left == null && root.right == null){
            if(left) res += root.val;
            else return;
        }
        help(root.left, true);
        help(root.right, false);
    }

#129 Sum Root to Leaf Numbers

Sol1 DFS+BackTracking

    int res = 0;
    public int sumNumbers(TreeNode root) {
        help(root, "");
        return res;
    }
    public void help(TreeNode root, String tmp){
        if(root == null) return;
        tmp = tmp + root.val;
        if(root.left == null && root.right == null) res += Integer.valueOf(tmp);
        help(root.left, tmp);
        help(root.right, tmp);
        tmp = tmp.substring(0, tmp.length()-1);
    }

优化 -- 不用String与int转化

    int res = 0;
    public int sumNumbers(TreeNode root) {
        help(root, 0);
        return res;
    }
    public void help(TreeNode root, int tmp){
        if(root == null) return;
        int cur = tmp * 10 + root.val;
        if(root.left == null && root.right == null) res += cur;
        help(root.left, cur);
        help(root.right, cur);
    }

#563 Binary Tree Tilt

Easy

Sol

    int res = 0;
    public int findTilt(TreeNode root) {
        help(root);
        return res;
    }
    public int help(TreeNode root){
        if(root == null) return 0;
        int left = help(root.left);
        int right = help(root.right);
        res += Math.abs(left - right);
        return left + right + root.val;
    }

[Leetcode][Tree--1]树相关题目汇总/分析/总结

[Binary Tree][Traversal]

#144 Binary Tree Preorder Traversal

#94 Binary Tree Inorder Traversal

#145 Binary Tree Postorder Traversal

#102 Binary Tree Level Order Traversal

#107 Binary Tree Level Order Traversal II

#103 Binary Tree Zigzag Level Order Traversal

#105 Construct Binary Tree from Preorder and Inorder Traversal

#106 Construct Binary Tree from Inorder and Postorder Traversal

[Binary Tree][Path]

#124 Binary Tree Maximum Path Sum

#257 Binary Tree Paths

#112 Path Sum

#113 Path Sum II

#437 Path Sum III

[Binary Tree][Verify/Modify]

#110 Balanced Binary Tree

#226 Invert Binary Tree

#199 Binary Tree Right Side View

#114 Flatten Binary Tree to Linked List

#331 Verify Preorder Serialization of a Binary Tree

[Binary Tree][Depth]

#111 Minimum Depth of Binary Tree

#104 Maximum Depth of Binary Tree

#662 Maximum Width of Binary Tree

[Binary Tree][Sum]

#404 Sum of Left Leaves

#129 Sum Root to Leaf Numbers

#563 Binary Tree Tilt

猜你喜欢

热点阅读