-
- Binary Tree Preorder Traversal
题目:对一棵二叉树进行前序遍历,并将结果存在一个List
思路:使用递归
细节:
对于递归版本:注意preorderTraversal() function 返回的是一个List, 所以不正直接用 res.add(root.val), preorderTraversal(root.left), preorderTraversal(root.right)来直接遍历
对于非递归版本:使用stack数据结构来辅助遍历,根左右的遍历顺序 对于栈操作需要反向按照根右左的顺序来压入栈
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
// null or leaf
if (root == null) {
return result;
}
// Divide
ArrayList<Integer> left = preorderTraversal(root.left);
ArrayList<Integer> right = preorderTraversal(root.right);
// Conquer
result.add(root.val);
result.addAll(left);
result.addAll(right);
return result;
}
}
-
- Lowest Common Ancestor of a Binary Tree
LCA
思路: divide and conquer
什么时候返回 root? -> (root == p || root == q)
什么时候返回 left ? -> left != null && right == null
什么时候返回 right ? -> right != null && left == null
-
- Lowest Common Ancestor of a Binary Search Tree
要利用BST的特性来提高搜索过程的效率
- Lowest Common Ancestor of a Binary Search Tree