Binary Tree前中后序遍历要弄清楚（有template）
可以看recursion整理pre/post/in-order的思路，但是面试会考iteration
In-order
void inOrderTraversal(TreeNode node) {
if (node != null) {
inOrderTraversal(node.left);
visit(node);
inOrderTraversal(node.right);
}
}
Pre-order
void preOrderTraversal(TreeNode node) {
if (node != null) {
visit(node);
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
Post-order
void postOrderTraversal(TreeNode node) {
if (node != null) {
inOrderTraversal(node.left);
inOrderTraversal(node.right);
visit(node);
}
}
postorder traversal
必背模板 将if条件与push right / push left 变换位置，则变成pre-order和in-order
public class Solution {
/**
* @param root: A Tree
* @return: Postorder in ArrayList which contains node values.
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
if(node != null) {
if(node.left == null && node.right == null) {
res.add(node.val);
} else {
stack.push(new TreeNode(node.val));
}
stack.push(node.right);
stack.push(node.left);
}
}
return res;
}
}
preorder不需要判断内if-loop
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
stack.push(node.right);
stack.push(node.left);
}
}
return res;
}
}
Binary Search Tree to Greater Sum Tree
- 本身是要求一个从右到左的中序遍历
- 要求modify the tree
-
可以先用一个list按顺序存了所有树节点，最后遍历这个list修改value
- 用了上面的模板行不通，因为上面的模板会重新放一个new TreeNode()在stack中，再一次pop时，改变的是new TreeNode的value，原先的树没有被改变
- 另一种中序遍历的方法，以这道题的从右到左为例：
- 先不停地往右边遍历，依次压栈，直到
TreeNode == null - 弹栈的过程中，如果有左子树就往左。
- 想象一下：先冲到树的最右下角，然后往回往上走，遇到了岔路就去左子树看看（又是一个重新的循环，在左子树里面冲到最右下角…)
- 先不停地往右边遍历，依次压栈，直到
- 所以整个while loop的退出条件是
TreeNode == null && stack.isEmpty()这代表的就是整棵树左下角 - 再也没有没有左子树（因为左子树一开始不在stack里），stack也没有内存了，就是遍历完了
- 内循环的第一个while loop就是为了向右一冲到底（途中要压栈）
- 代码实现
Stack <TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.empty()) { while (curr != null) { stack.push(curr); curr = curr.right; } curr = stack.pop(); list.add(curr); curr = curr.left; }
