@Yano 2019-09-20T02:56:40.000000Z 字数 27264 阅读 7185

# LeetCode之Tree题目汇总

LeetCode

# 公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

LeetCode 题目汇总

# Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

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

# Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1    \     2    /   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

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

# Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1    \     2    /   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

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

# Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1    \     2    /   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

    public class PostTreeNode {        TreeNode node;        boolean first;    }    public List<Integer> postorderTraversal(TreeNode root) {        List<Integer> rt = new ArrayList<Integer>();        if (root == null) {            return rt;        }        Stack<PostTreeNode> stack = new Stack<PostTreeNode>();        TreeNode p = root;        PostTreeNode t;        while (p != null || !stack.empty()) {            while (p != null) {                // 新建一个结点，这个结点包含一个布尔值first                // 用来判断是否是第一次入栈                PostTreeNode post = new PostTreeNode();                post.node = p;                post.first = true;                stack.push(post);                p = p.left;            }            if (!stack.empty()) {                t = stack.pop();                // 如果结点第一次出栈，再次入栈，将first置为false                if (t.first == true) {                    t.first = false;                    stack.push(t);                    p = t.node.right;                } else {                    rt.add(t.node.val);                    p = null;                }            }        }        return rt;    }

# Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   / \  9  20    /  \   15   7

return its level order traversal as:

[  [3],  [9,20],  [15,7]]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

1. 通过统计每一行的结点数

toBePrinted：当前待打印结点的数量
nextLevel：下一层的结点数量

2. 插入特殊结点

a queue stores [step0, step1, step2, ...]queue.add(first step)while queue is not empty  current_step = queue.poll()  // do something here with current_step  // like counting  foreah step in current_step can jump to    queue.add(step)

    public List<List<Integer>> levelOrder(TreeNode root) {        List<List<Integer>> rt = new ArrayList<List<Integer>>();        if (root == null) {            return rt;        }        Deque<TreeNode> deque = new LinkedList<TreeNode>();        deque.add(root);        int toBePrinted = 1;        int nextLevel = 0;        List<Integer> level = new LinkedList<Integer>();        while (!deque.isEmpty()) {            TreeNode p = deque.poll();            level.add(p.val);            toBePrinted--;            if (p.left != null) {                deque.addLast(p.left);                nextLevel++;            }            if (p.right != null) {                deque.addLast(p.right);                nextLevel++;            }            if (toBePrinted == 0) {                toBePrinted = nextLevel;                nextLevel = 0;                rt.add(new ArrayList<Integer>(level));                level.clear();            }        }        return rt;    }

    public List<List<Integer>> levelOrder2(TreeNode root) {        List<List<Integer>> rt = new ArrayList<List<Integer>>();        if (root == null) {            return rt;        }        final TreeNode END = new TreeNode(0);        Deque<TreeNode> deque = new LinkedList<TreeNode>();        List<Integer> level = new LinkedList<Integer>();        deque.add(root);        deque.add(END);        while (!deque.isEmpty()) {            TreeNode p = deque.pop();            if (p == END) {                rt.add(new ArrayList<Integer>(level));                level.clear();                if (!deque.isEmpty()) {                    deque.add(END);                }            } else {                level.add(p.val);                if (p.left != null) {                    deque.add(p.left);                }                if (p.right != null) {                    deque.add(p.right);                }            }        }        return rt;    }

# Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   / \  9  20    /  \   15   7

return its bottom-up level order traversal as:

[  [15,7],  [9,20],  [3]]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Collections.reverse(result);
    public List<List<Integer>> levelOrderBottom(TreeNode root) {        List<List<Integer>> rt = new ArrayList<List<Integer>>();        if (root == null) {            return rt;        }        final TreeNode END = new TreeNode(0);        Deque<TreeNode> deque = new LinkedList<TreeNode>();        List<Integer> level = new LinkedList<Integer>();        deque.add(root);        deque.add(END);        while (!deque.isEmpty()) {            TreeNode p = deque.pop();            if (p == END) {                rt.add(new ArrayList<Integer>(level));                level.clear();                if (!deque.isEmpty()) {                    deque.add(END);                }            } else {                level.add(p.val);                if (p.left != null) {                    deque.add(p.left);                }                if (p.right != null) {                    deque.add(p.right);                }            }        }        Collections.reverse(rt);        return rt;    }

# Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1 /   \2     3 \  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

    List<String> rt = new ArrayList<String>();    List<Integer> path = new ArrayList<Integer>();    public List<String> binaryTreePaths(TreeNode root) {        findPath(root);        return rt;    }    void findPath(TreeNode root) {        if (root == null) {            return;        }        path.add(root.val);        // 是一条路径，将path添加到rt中        if (root.left == null && root.right == null) {            StringBuffer sb = new StringBuffer();            sb.append(path.get(0));            for (int i = 1; i < path.size(); i++) {                sb.append("->" + path.get(i));            }            rt.add(sb.toString());        }        findPath(root.left);        findPath(root.right);        path.remove(path.size() - 1);    }

# Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <--- /   \2     3         <--- \     \  5     4       <---

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

1. 递归求解

   1            <--- /   \2     3         <--- \     \  5     4       <---   \    6           <---

list1是[1, 3, 4], list2是[1, 2, 5, 6]。list2比list1长，长出的部分是6，也在结果之中。

2. 插入特殊结点

3. 计数法

toBePrinted：当前待打印结点的数量
nextLevel：下一层的结点数量

    public List<Integer> rightSideView(TreeNode root) {        List<Integer> rt = new ArrayList<Integer>();        if (root == null) {            return rt;        }        rt.add(root.val);        List<Integer> left = rightSideView(root.left);        List<Integer> right = rightSideView(root.right);        rt.addAll(right);        if (left.size() > right.size()) {            rt.addAll(left.subList(right.size(), left.size()));        }        return rt;    }

    public List<Integer> rightSideView2(TreeNode root) {        List<Integer> rt = new ArrayList<Integer>();        if (root == null) {            return rt;        }        final TreeNode END = new TreeNode(0);        Deque<TreeNode> deque = new LinkedList<TreeNode>();        deque.add(root);        deque.add(END);        while (!deque.isEmpty()) {            TreeNode p = deque.pop();            if (p == END) {                if (!deque.isEmpty()) {                    deque.add(END);                }            } else {                // 如果deque的下一个是END，则p是层序的最后一个，加入结果rt                if (deque.peek() == END) {                    rt.add(p.val);                }                if (p.left != null) {                    deque.add(p.left);                }                if (p.right != null) {                    deque.add(p.right);                }            }        }        return rt;    }

    public List<Integer> rightSideView3(TreeNode root) {        List<Integer> rt = new ArrayList<Integer>();        if (root == null) {            return rt;        }        Deque<TreeNode> deque = new LinkedList<TreeNode>();        deque.add(root);        int toBePrinted = 1;        int nextLevel = 0;        List<Integer> level = new LinkedList<Integer>();        while (!deque.isEmpty()) {            TreeNode p = deque.poll();            level.add(p.val);            toBePrinted--;            if (p.left != null) {                deque.addLast(p.left);                nextLevel++;            }            if (p.right != null) {                deque.addLast(p.right);                nextLevel++;            }            if (toBePrinted == 0) {                toBePrinted = nextLevel;                nextLevel = 0;                rt.add(p.val);                level.clear();            }        }        return rt;    }

# Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   / \  9  20    /  \   15   7

return its zigzag level order traversal as:

[  [3],  [20,9],  [15,7]]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {        List<List<Integer>> rt = new ArrayList<List<Integer>>();        if (root == null) {            return rt;        }        final TreeNode END = new TreeNode(0);        Deque<TreeNode> deque = new LinkedList<TreeNode>();        List<Integer> level = new LinkedList<Integer>();        int count = 0;        deque.add(root);        deque.add(END);        while (!deque.isEmpty()) {            TreeNode p = deque.pop();            if (p == END) {                if (count % 2 == 1) {                    Collections.reverse(level);                }                count++;                rt.add(new ArrayList<Integer>(level));                level.clear();                if (!deque.isEmpty()) {                    deque.add(END);                }            } else {                level.add(p.val);                if (p.left != null) {                    deque.add(p.left);                }                if (p.right != null) {                    deque.add(p.right);                }            }        }        return rt;    }

# Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

    int p;    int[] postorder;    int[] inorder;    public TreeNode buildTree(int[] inorder, int[] postorder) {        this.p = postorder.length - 1;        this.inorder = inorder;        this.postorder = postorder;        return buildTree(0, postorder.length);    }    TreeNode buildTree(int start, int end) {        if (start >= end) {            return null;        }        TreeNode root = new TreeNode(postorder[p]);        int i;        for (i = start; i < end && postorder[p] != inorder[i]; i++)            ;        p--;        root.right = buildTree(i + 1, end);        root.left = buildTree(start, i);        return root;    }

# Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

    int p = 0;    int[] preorder;    int[] inorder;    public TreeNode buildTree(int[] preorder, int[] inorder) {        this.preorder = preorder;        this.inorder = inorder;        return buildTree(0, preorder.length);    }    TreeNode buildTree(int start, int end) {        if (start >= end) {            return null;        }        TreeNode root = new TreeNode(preorder[p]);        int i;        for (i = start; i < end && preorder[p] != inorder[i]; i++)            ;        p++;        root.left = buildTree(start, i);        root.right = buildTree(i + 1, end);        return root;    }

# Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

        int mid = (start + end) / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = buildBST(start, mid);        root.right = buildBST(mid + 1, end);
    int[] nums;    public TreeNode sortedArrayToBST(int[] nums) {        this.nums = nums;        return buildBST(0, nums.length);    }    TreeNode buildBST(int start, int end) {        if (start >= end) {            return null;        }        int mid = (start + end) / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = buildBST(start, mid);        root.right = buildBST(mid + 1, end);        return root;    }    public TreeNode sortedArrayToBST2(int[] nums) {        if (nums.length == 0) {            return null;        }        if (nums.length == 1) {            return new TreeNode(nums[0]);        }        int mid = nums.length / 2;        TreeNode root = new TreeNode(nums[mid]);        root.left = sortedArrayToBST2(Arrays.copyOfRange(nums, 0, mid));        root.right = sortedArrayToBST2(Arrays.copyOfRange(nums, mid + 1,                nums.length));        return root;    }

# Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

    public int countNodes(TreeNode root) {        if (root == null) {            return 0;        }        int leftHeight = 0;        int rightHeight = 0;        // 计算leftHeight        TreeNode p = root;        while (p != null) {            p = p.left;            leftHeight++;        }        // 计算rightHeight        p = root;        while (p != null) {            p = p.right;            rightHeight++;        }        // 如果相等，满足2^n-1        if (leftHeight == rightHeight) {            return (1 << leftHeight) - 1;        }        return 1 + countNodes(root.left) + countNodes(root.right);    }

# Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1        / \       2   5      / \   \     3   4   6

The flattened tree should look like:

   1    \     2      \       3        \         4          \           5            \             6

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

    TreeNode prev;    void preorder(TreeNode root) {        if (root == null)            return;        TreeNode left = root.left;        TreeNode right = root.right;        // root        if (prev != null) {            prev.right = root;            prev.left = null;        }        prev = root;        preorder(left);        preorder(right);    }    public void flatten(TreeNode root) {        prev = null;        preorder(root);    }

# Invert Binary Tree

Invert a binary tree.

     4   /   \  2     7 / \   / \1   3 6   9

to

     4   /   \  7     2 / \   / \9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

    public TreeNode invertTree(TreeNode root) {        if ((root == null) || (root.left == null && root.right == null)) {            return root;        }        TreeNode tmp = root.left;        root.left = root.right;        root.right = tmp;        if (root.left != null) {            invertTree(root.left);        }        if (root.right != null) {            invertTree(root.right);        }        return root;    }

# Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the **k**th smallest element in it.

**Note: **
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

1. Try to utilize the property of a BST.
2. What if you could modify the BST node's structure?
3. The optimal runtime complexity is O(height of BST).

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

    public int kthSmallest(TreeNode root, int k) {        if (root == null) {            return -1;        }        Stack<TreeNode> stack = new Stack<TreeNode>();        TreeNode p = root;        while (p != null || !stack.isEmpty()) {            while (p != null) {                stack.push(p);                p = p.left;            }            if (!stack.isEmpty()) {                p = stack.pop();                if (--k == 0) {                    return p.val;                }                p = p.right;            }        }        return 0;    }

# Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______       /              \    ___2__          ___8__   /      \        /      \   0      _4       7       9         /  \         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

BST，性质是：根结点都比左结点大，比右结点小。所以给定两个结点，找公共祖先，就是找值在两个结点间的结点。

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        if (root == null || p == null || q == null) {            return null;        }        int m = Math.min(p.val, q.val);        int n = Math.max(p.val, q.val);        while (root != null) {            if (root.val < m) {                root = root.right;            } else if (root.val > n) {                root = root.left;            } else {                return root;            }        }        return null;    }

# Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______       /              \    ___5__          ___1__   /      \        /      \   6      _2       0       8         /  \         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

http://www.fusu.us/2013/06/p2-lowest-common-ancestor-in-binary-tree.html

1. 从叶结点开始，向上搜索
2. 对于每一个结点node

• l：node的左子树是否出现过p或q
• r：node的右子树是否出现过p或q
3. 如果l和r都不是null，则该结点即为lca

1. l=null, r=null：node不含有p和q中的任意一个
2. l!=null, r=null：node左子树含有其中一个
3. l=null, r!=null：node右子树含有其中一个
4. l!=null, r!=null：node左、右子树各有其中一个（由于是从叶节点向根结点搜索，所以最先出现该情况的结点，必为lca）

        -1       /  \      0    3     / \   -2   4   /  8

1. 首先进入结点-1，0，-2
2. 在结点-2时，-2的左结点是8，是其中一个结点，则l置为8，不为空。-2的右结点是null，r仍然是null。表面-2不是lca
3. 进入结点0，此时l已经不是null，0的右结点是4，是其中一个结点，则r置为4，不为空。
4. 此时，l和r都不为null，0就是lca
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        // 发现目标结点，则标记（left或right）        if (root == null || root == p || root == q)            return root;        // 查看左右子树是否有目标结点        TreeNode left = lowestCommonAncestor(root.left, p, q);        TreeNode right = lowestCommonAncestor(root.right, p, q);        // 左右子树同时含有目标结点，则该结点是lca        if (left != null && right != null)            return root;        // 左右子树只有一个含有目标结点，向上返回        return left == null ? right : left;    }

# Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

    public int maxDepth(TreeNode root) {        if (root == null) {            return 0;        }        int nLeft = maxDepth(root.left);        int nRight = maxDepth(root.right);        return nLeft > nRight ? (nLeft + 1) : (nRight + 1);    }

# Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Minimum Depth的定义如下：

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

# Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5             / \            4   8           /   / \          11  13  4         /  \      \        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

    boolean hasPath;    public boolean hasPathSum(TreeNode root, int sum) {        if (root == null) {            return false;        }        hasPath = false;        help(root, 0, sum);        return hasPath;    }    void help(TreeNode node, int cur, int sum) {        cur += node.val;        boolean isLeaf = (node.left == null) && (node.right == null);        if (cur == sum && isLeaf) {            hasPath = true;        }        if (node.left != null) {            help(node.left, cur, sum);        }        if (node.right != null) {            help(node.right, cur, sum);        }        cur -= node.val;    }

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

# Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

return

[   [5,4,11,2],   [5,8,4,5]]

    List<List<Integer>> result;    List<Integer> path;    int sum;    public List<List<Integer>> pathSum(TreeNode root, int sum) {        result = new ArrayList<List<Integer>>();        path = new ArrayList<Integer>();        this.sum = sum;        if (root == null) {            return result;        }        help(root, 0);        return result;    }    void help(TreeNode node, int cur) {        cur += node.val;        path.add(node.val);        boolean isLeaf = (node.left == null) && (node.right == null);        if (cur == sum && isLeaf) {            result.add(new ArrayList<Integer>(path));        }        if (node.left != null) {            help(node.left, cur);        }        if (node.right != null) {            help(node.right, cur);        }        cur -= node.val;        path.remove(path.size() - 1);    }

# Populating Next Right Pointers in Each Node

Given a binary tree

 struct TreeLinkNode {
}


Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1       /  \      2    3     / \  / \    4  5  6  7

After calling your function, the tree should look like:

        1 -> NULL       /  \      2 -> 3 -> NULL     / \  / \    4->5->6->7 -> NULL

    public class TreeLinkNode {        int val;        TreeLinkNode left, right, next;        TreeLinkNode(int x) {            val = x;        }    }    public void connect(TreeLinkNode root) {        if (root == null) {            return;        }        if (root.left != null && root.right != null) {            root.left.next = root.right;        }        if (root.next != null && root.next.left != null) {            root.right.next = root.next.left;        }        connect(root.left);        connect(root.right);    }

# Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

    public boolean isSameTree(TreeNode p, TreeNode q) {        if (p == null && q == null) {            return true;        } else if (p == null || q == null) {            return false;        }        return p.val == q.val && isSameTree(p.left, q.left)                && isSameTree(p.right, q.right);    }

# Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1   / \  2   2 / \ / \3  4 4  3

But the following is not:

    1   / \  2   2   \   \   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

    // recursively    public boolean isSymmetric(TreeNode root) {        if (root == null) {            return true;        }        return isSymmetric(root.left, root.right);    }    boolean isSymmetric(TreeNode p, TreeNode q) {        if (p == null && q == null) {            return true;        } else if (p == null || q == null) {            return false;        }        return p.val == q.val && isSymmetric(p.left, q.right)                && isSymmetric(p.right, q.left);    }

    // iteratively    public boolean isSymmetric2(TreeNode root) {        if (root == null) {            return true;        }        Deque<TreeNode> deque = new LinkedList<TreeNode>();        if (root.left == null && root.right == null) {            return true;        } else if (root.left == null || root.right == null) {            return false;        } else {            deque.addLast(root.left);            deque.addLast(root.right);        }        while (deque.size() != 0) {            TreeNode p = deque.pop();            TreeNode q = deque.pop();            if (p.val != q.val) {                return false;            }            if (p.left == null && q.right == null) {                // do nothing            } else if (p.left == null || q.right == null) {                return false;            } else {                deque.addLast(p.left);                deque.addLast(q.right);            }            if (p.right == null && q.left == null) {                // do nothing            } else if (p.right == null || q.left == null) {                return false;            } else {                deque.addLast(p.right);                deque.addLast(q.left);            }        }        return true;    }

# Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1   / \  2   3     / \    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.

    1   / \  2   3     /     4      /  5
    public String serialize(TreeNode root) {        if (root == null) {            return "";        }        StringBuffer sb = new StringBuffer();        Deque<TreeNode> deque = new LinkedList<TreeNode>();        deque.add(root);        while (!deque.isEmpty()) {            TreeNode p = deque.pop();            if (p == null) {                sb.append(",#");            } else {                sb.append("," + p.val);                deque.add(p.left);                deque.add(p.right);            }        }        // 第一个元素前也有一个逗号，截取        return sb.toString().substring(1);    }    public TreeNode deserialize(String data) {        if (data == null || data.length() == 0) {            return null;        }        String[] s = data.split(",");        TreeNode[] node = new TreeNode[s.length];        // 新建TreeNode，并初始化        for (int i = 0; i < node.length; i++) {            if (!"#".equals(s[i])) {                node[i] = new TreeNode(Integer.valueOf(s[i]));            }        }        int parent = 0;        // 将结点连接起来        for (int i = 0; parent * 2 + 2 < s.length; i++) {            if (node[i] != null) {                node[i].left = node[parent * 2 + 1];                node[i].right = node[parent * 2 + 2];                parent++;            }        }        return node[0];    }

# Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1   / \  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

    int sumNumbers(TreeNode root, int parentval) {        if (root == null) {            return 0;        }        int p = parentval * 10 + root.val;        if (root.left == null && root.right == null) {            return p;        }        return sumNumbers(root.left, p) + sumNumbers(root.right, p);    }

# Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3

1. 以n为根结点的二叉树个数=左子树个数*右子树个数
2. 用数组record[n+1]记录以0~n的情况，自底向上，否则会超时
    public int numTrees(int n) {        if (n == 1 || n == 2) {            return n;        }        // record[0]没有用，所以长度是n+1        // 使用数组，从下向上保存结果，能够节省时间，否则会超时        int[] record = new int[n + 1];        record[0] = 1;        record[1] = 1; // 1个元素时，情况为1        record[2] = 2; // 2个元素时，情况为2        for (int i = 3; i <= n; i++) {            int tmp = 0;            for (int k = 0; k < i; k++) {                // 以n为根结点的二叉树个数=左结点的二叉树个数*右结点的二叉树个数                // 题目所求要包括所有情况，分别以1~n为根结点                tmp += (record[k] * record[i - k - 1]);            }            // 记录1~i时，BST的个数            record[i] = tmp;        }        return record[n];    }

# Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

    public List<TreeNode> generateTrees(int n) {        int[] array = new int[n];        // 建立1~n的数组        for (int i = 0; i < n; i++) {            array[i] = i + 1;        }        return generateTrees(array);    }    List<TreeNode> generateTrees(int[] array) {        if (array.length == 0) {            return new ArrayList<TreeNode>(                    Collections.<TreeNode> singletonList(null));        }        ArrayList<TreeNode> rt = new ArrayList<TreeNode>();        // 数组的每一个元素（array[i]），分别作为根结点        for (int i = 0; i < array.length; i++) {            // array[i]作为根结点，array[i]之前的元素为左结点，array[i]之后的元素为右结点            for (TreeNode left : generateTrees(Arrays.copyOfRange(array, 0, i))) {                for (TreeNode right : generateTrees(Arrays.copyOfRange(array,                        i + 1, array.length))) {                    TreeNode root = new TreeNode(array[i]);                    root.left = left;                    root.right = right;                    rt.add(root);                }            }        }        return rt;    }

# Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

    boolean failed = false;    // 要用long，而不是int    // 否则涉及到Integer.MIN_VALUE的用例会出现错误    // 比如{Integer.MIN_VALUE}这个用例会错误    long last = Long.MIN_VALUE;    public boolean isValidBST(TreeNode root) {        if (root == null) {            return true;        }        inorder(root);        return !failed;    }    private void inorder(TreeNode root) {        if (root == null || failed) {            return;        }        // 左        inorder(root.left);        // 中，相当于中序遍历中的打印操作        // 只采用了一个变量，所以空间复杂度是O(1)        // 传统的做法是建立一个ArrayList，然后判断中序遍历是否是递增的，但是空间复杂度是O(n)        if (last >= root.val) {            failed = true;        }        last = root.val;        // 右        inorder(root.right);    }

• 私有
• 公开
• 删除