105. Construct Binary Tree from Preorder and Inorder Traversal --- Medium
106. Construct Binary Tree from Inorder and Postorder Traversal --- Medium
199. Binary Tree Right Side View --- Medium
107. Binary Tree Level Order Traversal II --- Medium
TreeNode定义
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
1. 构造二叉树，根据先序遍历和中序遍历 （Leetcode 105）
Leetcode 105
思路 ：
public TreeNode buildTree(int[] preorder, int[] inorder)
步骤1:
根结点必定是preorder[0] 即3.
再去找左子树，即inorder数组中，数值3左侧的部分。
右子树，即inorder数组中，数值3右侧的部分。
步骤2：
分别对左子树，右子树进行递归处理。
步骤3:
最终子树中只有1个结点时，说明子树中只有这一个结点，直接将此结点返回。
2. 构造二叉树，根据中序遍历和后序遍历 （Leetcode 106）
Leetcode 106
思路：
postorder的最后一个结点，就是根结点。
那么inorder可以被拆分成左子树，右子树，再去分别递归。
3. 二叉树的右侧视角 （Leetcode 199）
Leetcode 199
思路：
按层次遍历树，找到每一层的最后一个结点。
用一个queue来存放遍历结点。
queue的基本操作，offer入队，poll出队，peek看队列第一个元素，size看队列大小。
4. 二叉树的层次遍历-由底而上 （Leetcode 107）
Leetcode 199
思路：
层次遍历，queue用来遍历。
用一个栈，存放List<Integer>即从上往下一层的结点。
最后从栈中弹出，形成最终解。
