Leetcode的105、106、889这三题的解题思路都是一样的，主要是注意一下两点：
1、三个题目迭代构建子树的区间变化
2、三个题目创建树的根节点是不样的
Leetcode106题 中序+后序
Leetcode105题 前序+后序
Leetcode889题 前序+中序
例题
1.前序遍历二叉树
描述
思路
- 递归
- 栈
代码
Python-非递归：
class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:sta = []res = []if not root:return ressta.append(root)while sta:node = sta.pop()res.append(node.val)if node.right:sta.append(node.right)if node.left:sta.append(node.left)return res
Java-非递归：
class Solution {public List<Integer> preorderTraversal(TreeNode root) {Deque<TreeNode> stack = new ArrayDeque<>();List<Integer> res = new ArrayList<>();if (root == null) return res;stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();res.add(node.val);if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}}return res;}}
JavaScript非递归
/*** Definition for a binary tree node.* function TreeNode(val) {* this.val = val;* this.left = this.right = null;* }*//*** @param {TreeNode} root* @return {number[]}*/var preorderTraversal = function(root) {let res = new Array();if (root == null) return res;let sta = new Array();sta.push(root);while (sta.length > 0) {let node = sta.pop();res.push(node.val);if (node.right != null) {sta.push(node.right);}if (node.left != null) {sta.push(node.left);}}return res;};
Python递归：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def in_order(root):
if not root:
return
res.append(root.val)
in_order(root.left)
in_order(root.right)
res = []
in_order(root)
return res
Java递归：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(res, root);
return res;
}
public void dfs(List<Integer> res, TreeNode node) {
if (node == null) return;
res.add(node.val);
dfs(res, node.left);
dfs(res, node.right);
}
}
2.中序遍历二叉树
描述 
思路
- 递归
- 迭代
代码
Python非迭代：
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
res = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
Java非迭代：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
Stack < TreeNode > stack = new Stack < > ();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}
JavaScipt迭代：
var inorderTraversal = function(root) {
let res = [];
let sta = [];
let cur = root;
while (sta.length > 0 || cur != null) {
while (cur != null) {
sta.push(cur);
cur = cur.left;
}
cur = sta.pop();
res.push(cur.val);
cur = cur.right;
}
return res;
};
Python递归：
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
def dfs(root):
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
res = []
dfs(root)
return res
3.后序遍历二叉树
思路
- 递归
- 迭代
前序遍历是 根 ->左 ->右 依然使用前序遍历，不过左右孩子的进战顺序换掉，最后逆序输出就是后序遍历的结果。
代码
Python代码：
def postorderTraversal(self, root: TreeNode) -> List[int]:
sta = []
res = []
if not root:
return res
sta.append(root)
while sta:
node = sta.pop()
res.append(node.val)
if node.left:
sta.append(node.left)
if node.right:
sta.append(node.right)
return res[::-1]
Java代码：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
if (root == null) {
return res;
}
stack.addLast(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
res.addFirst(node.val);
if (node.left != null) stack.addLast(node.left);
if (node.right != null) stack.addLast(node.right);
}
return res;
}
}
JavaScript代码：
var postorderTraversal = function(root) {
if (root === null) {
return []
}
const sta = [];
const res = [];
sta.push(root);
while (sta.length > 0) {
const node = sta.pop();
res.unshift(node.val);
node.left && sta.push(node.left);
node.right && sta.push(node.right);
}
return res;
};
Python递归代码：
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
res.append(root.val)
res = []
dfs(root)
return res
4. lc 105. 从前序与中序遍历序列构造二叉树
思路
- 递归
- 找到根节点对应的索引位置，将前序后中序左右孩子的对应部分划分出来
- 递归调用函数，连接左右子孩子，递归返回值为节点。
这类问题在 Facebook 的面试中常常出现，它可以在 \mathcal{O}(N)O(N) 的时间内解决：
通常从先序序列或者后序序列开始，根据不同遍历方法的规律，选择合适的节点构造树。
例如：先序序列的 第一个 节点是根节点，然后是它的左孩子，右孩子等等。
后序序列的 最后一个 节点是根节点，然后是它的右孩子，左孩子等等。
从先序/后序序列中找到根节点，根据根节点将中序序列分为左子树和右子树。从中序序列中获得的信息是：如果当前子树为空（返回 None），否则继续构造子树。
代码
Python代码：
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not preorder or not inorder:
return None
root_value = preorder[0]
root = TreeNode(root_value)
root_index = inorder.index(root_value)
root.left = self.buildTree(preorder[1:], inorder[:root_index])
root.right = self.buildTree(preorder[root_index+1:], inorder[root_index+1:])
return root
Java代码：
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inLen; i++){
map.put(inorder[i], i);
}
return buildTree(map,preorder, inorder, 0, preLen - 1, 0, inLen - 1);
}
public TreeNode buildTree(Map<Integer, Integer> map, int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
int rootVal = preorder[preLeft];
TreeNode root = new TreeNode(rootVal);
int pIndex = map.get(rootVal);
root.left = buildTree(map, preorder, inorder, preLeft + 1, pIndex - inLeft + preLeft, inLeft, pIndex-1);
root.right = buildTree(map, preorder, inorder, pIndex - inLeft + preLeft + 1, preRight, pIndex + 1, inRight);
return root;
}
}
JavaScript代码：
var buildTree = function(preorder, inorder) {
function helper(preorder, inorder, preLeft, preRight, inLeft, inRight) {
if (preLeft > preRight || inLeft > inRight) {
return null;
}
let rootValue = preorder[preLeft];
let rootIndex = inorder.indexOf(rootValue);
let root = new TreeNode(rootValue);
root.left = helper(preorder, inorder, preLeft + 1, rootIndex - inLeft + preLeft, inLeft, rootIndex-1)
root.right = helper(preorder, inorder, rootIndex - inLeft + preLeft + 1,preRight, rootIndex + 1, inRight)
return root;
}
return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
};
5. lc 106. 从中序与后序遍历序列构造二叉树
思路
- 创建 hashmap 存储中序序列：value -> its index 。
- 方法 helper 的参数是中序序列中当前子树的左右边界，该方法仅用于检查子树是否为空。下面分析 helper(in_left = 0, in_right = n - 1) 的逻辑：
- 如果 in_left > in_right，说明子树为空，返回 None。
- 选择后序遍历的最后一个节点作为根节点。
- 假设根节点在中序遍历中索引为 index。从 in_left 到 index - 1 属于左子树，从 index + 1 到 in_right 属于右子树。
- 根据后序遍历逻辑，递归创建右子树 helper(index + 1, in_right) 和左子树 helper(in_left, index - 1)。
- 返回根节点 root。
代码
class Solution {
int post_idx;
int[] postorder;
int[] inorder;
HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();
public TreeNode helper(int in_left, int in_right) {
// if there is no elements to construct subtrees
if (in_left > in_right)
return null;
// pick up post_idx element as a root
int root_val = postorder[post_idx];
TreeNode root = new TreeNode(root_val);
// root splits inorder list
// into left and right subtrees
int index = idx_map.get(root_val);
// recursion
post_idx--;
// build right subtree
root.right = helper(index + 1, in_right);
// build left subtree
root.left = helper(in_left, index - 1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.inorder = inorder;
// start from the last postorder element
post_idx = postorder.length - 1;
// build a hashmap value -> its index
int idx = 0;
for (Integer val : inorder)
idx_map.put(val, idx++);
return helper(0, inorder.length - 1);
}
}
Python代码：
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
def helper(in_left, in_right):
# if there is no elements to construct subtrees
if in_left > in_right:
return None
# pick up the last element as a root
val = postorder.pop()
root = TreeNode(val)
# root splits inorder list
# into left and right subtrees
index = idx_map[val]
# build right subtree
root.right = helper(index + 1, in_right)
# build left subtree
root.left = helper(in_left, index - 1)
return root
# build a hashmap value -> its index
idx_map = {val:idx for idx, val in enumerate(inorder)}
return helper(0, len(inorder) - 1)
JavaScript代码：
var buildTree = function(inorder, postorder) {
let idx = 0;
let dic = new Map();
for (let val of inorder) {
dic.set(val, idx++)
}
let postIdx = postorder.length - 1;
function helper(inLeft, inRight) {
if (inLeft > inRight) {
return null;
}
let rootVal = postorder[postIdx];
let root = new TreeNode(rootVal);
postIdx--;
let rootIndex = dic.get(rootVal);
root.right = helper(rootIndex + 1, inRight);
root.left = helper(inLeft, rootIndex - 1)
return root;
}
let res = helper(0, inorder.length - 1);
return res;
};
6. lc 889. 根据前序和后序遍历构造二叉树
思路
前序遍历为：
(根结点) (前序遍历左分支) (前序遍历右分支)
而后序遍历为：
(后序遍历左分支) (后序遍历右分支) (根结点)
例如，如果最终的二叉树可以被序列化的表述为 [1, 2, 3, 4, 5, 6, 7]，那么其前序遍历为 [1] + [2, 4, 5] + [3, 6, 7]，而后序遍历为 [4, 5, 2] + [6, 7, 3] + [1].
如果我们知道左分支有多少个结点，我们就可以对这些数组进行分组，并用递归生成树的每个分支。
我们令左分支有 L 个节点。我们知道左分支的头节点为 pre[1]，但它也出现在左分支的后序表示的最后。所以 pre[1] = post[L-1]（因为结点的值具有唯一性），因此 L = post.indexOf(pre[1]) + 1。
现在在我们的递归步骤中，左分支由 pre[1 : L+1] 和 post[0 : L] 重新分支，而右分支将由 pre[L+1 : N] 和 post[L : N-1] 重新分支。
代码
Python代码：
class Solution(object):
def constructFromPrePost(self, pre, post):
if not pre: return None
root = TreeNode(pre[0])
if len(pre) == 1: return root
L = post.index(pre[1]) + 1
root.left = self.constructFromPrePost(pre[1:L+1], post[:L])
root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])
return root
Java代码：
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
int N = pre.length;
if (N == 0) return null;
TreeNode root = new TreeNode(pre[0]);
if (N == 1) return root;
int L = 0;
for (int i = 0; i < N; ++i)
if (post[i] == pre[1])
L = i+1;
root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, L+1),
Arrays.copyOfRange(post, 0, L));
root.right = constructFromPrePost(Arrays.copyOfRange(pre, L+1, N),
Arrays.copyOfRange(post, L, N-1));
return root;
}
}
var constructFromPrePost = function(pre, post) {
let n = pre.length;
if (n == 0) return null;
let root = new TreeNode(pre[0]);
if (n == 1) return root;
let leftLen = post.indexOf(pre[1]) + 1;
root.left = constructFromPrePost(pre.slice(1, leftLen+1), post.slice(0, leftLen));
root.right = constructFromPrePost(pre.slice(leftLen+1, n), post.slice(leftLen, n-1))
return root;
};
7. lc 236. 二叉树的最近公共祖先
思路
- 递归
- 根节点开始遍历，递归返回的是bool值，当节点值为p.val或q.val时返回true
- 递归返回左右子树的p，q，存在情况。
- 记录全局值
- 深度优先搜索
- 两次dfs遍历找到从根节点到对应节点的路劲。
- 然后比较，路径上最后一个相等的节点，即为最近公共祖先。
代码
Java代码：
class Solution {
TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}
}
JavaScript代码：
var lowestCommonAncestor = function(root, p, q) {
if (root == null) return null;
let res;
function dfs(root, p, q) {
if (root === null) return null;
let lson = dfs(root.left, p, q);
let rson = dfs(root.right, p, q);
if ((lson && rson) || ((lson || rson) && (root.val === p.val || root.val === q.val))) {
res = root;
}
return (root.val === p.val || root.val === q.val) || lson || rson;
}
dfs(root, p, q);
return res;
};
Python代码：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def back(node, path, target, res):
if not node:
return
if node == target:
path.append(node)
res.extend(path[:]) # 注意用[:],即浅拷贝
return
path.append(node)
back(node.left, path, target, res) # 回溯
back(node.right, path, target, res)
path.pop() # 记得恢复状态
res_p = [] # 两个变量，分别存储从根到目标点的路径
res_q = []
back(root, [], p, res_p)
back(root, [], q, res_q)
# 让 res_p 存储路径较小的那个，方便下面遍历查找操作
if len(res_p) > len(res_q):
res_p, res_q = res_q, res_p
for i in range(len(res_p)):
if res_p[i] != res_q[i]:
if i > 0:
return res_p[i - 1]
elif i == 0:
return res_p[i]
return res_p[-1]
8. 二叉树转链表
思路
- 递归
- 栈
代码
Python递归
class Solution:
def __init__(self):
self.pre = None
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return
self.flatten(root.right)
self.flatten(root.left)
root.right = self.pre
root.left = None
self.pre = root;
Java代码：
class Solution {
public void flatten(TreeNode root) {
while (root != null) {
if (root.left == null) {
root = root.right;
} else {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root.right;
root.right = root.left;
root.left = null;
root = root.right;
}
}
}
}
JavaScript代码：
var flatten = function(root) {
if (root == null) return root;
let sta = [root]
let pre = new TreeNode(-1);
while (sta.length > 0) {
let temp = sta.pop();
pre.left = null;
pre.right = temp;
if (temp.right != null) {
sta.push(temp.right);
}
if (temp.left != null) {
sta.push(temp.left);
}
pre = pre.right;
}
};
9. 124. 二叉树中的最大路径和
Java代码：
class Solution {
int ans = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) return 0;
helper(root);
return ans;
}
public int helper(TreeNode root) {
if (root == null) return 0;
int left = Math.max(helper(root.left), 0);
int right = Math.max(helper(root.right), 0);
ans = Math.max(ans, root.val + left + right);
return root.val + Math.max(left, right);
}
}
Python代码：
class Solution:
def __init__(self):
self.max_sum = float('-inf')
def maxPathSum(self, root: TreeNode) -> int:
def helper(root):
if not root:
return 0
# 递归计算左右子节点的最大贡献值
# 只有在最大贡献值大于 0 时，才会选取对应子节点
left_gain = max(helper(root.left), 0)
right_gain = max(helper(root.right), 0)
# 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
price_new_path = root.val + left_gain + right_gain
# 更新答案
self.max_sum = max(self.max_sum, price_new_path)
return root.val + max(left_gain, right_gain)
helper(root)
return self.max_sum
10. lc 103. 二叉树的锯齿形层次遍历
思路
- 层序遍历
- 偶数层反向
代码
Python代码：
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
import collections
if not root:
return []
q = collections.deque()
q.append(root)
res = []
left_to_right = True
while q:
temp = []
for i in range(len(q)):
node = q.popleft()
temp.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if left_to_right:
res.append(temp)
else:
res.append(temp[::-1])
left_to_right = not left_to_right
return res
Java代码：
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
boolean left_to_right = true;
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
LinkedList<Integer> temp = new LinkedList();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
if (left_to_right) {
temp.addLast(node.val);
} else {
temp.addFirst(node.val);
}
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.add(temp);
left_to_right = !left_to_right;
}
return res;
}
}
JavaScript代码：
var zigzagLevelOrder = function(root) {
const res = [];
if (root == null) return res;
const queue = [];
queue.push(root);
let left_to_right = true;
while (queue.length > 0) {
const size = queue.length;
let temp = [];
for (let i = 0; i < size; i++) {
let node = queue.shift();
if (left_to_right) {
temp.push(node.val);
} else {
temp.unshift(node.val);
}
if (node.left != null) queue.push(node.left);
if (node.right != null) queue.push(node.right);
}
res.push(temp);
left_to_right = !left_to_right;
}
return res;
};
若有收获，就点个赞吧
0 人点赞
