144二叉树的前序遍历

思路

根据据条件，实现递归需要两步：
1.找出重复的子问题（递推公式）。
2.终止条件。
转换为:
(1) 找出重复的子问题
前序遍历的顺序是：根、左子树、右子树。
对于左子树或者右子树来说，也是同样的遍历顺序。
所以重复的子问题:先取根节点，再遍历左子树，最后遍历右子树。
(2) 确定终止条件
对于二叉树的遍历来说，想终止，即没东西遍历了，没东西遍历自然就停下来了。
那就是当前的节点是空的，既然是空的就没必要遍历了。

代码

class Solution {
    public void preOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preOrder(root, res);
        return res;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preOrder(self, root: TreeNode, res):
        if root == None:
            return
        res.append(root.val)
        self.preOrder(root.left, res)
        self.preOrder(root.right, res)
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.preOrder(root, res)
        return res

94二叉树的中序遍历

思路

中序遍历，按照 左-打印-右这种顺序遍历树即可
递归函数实现
终止条件：当前节点为空时
函数内：递归的调用左节点，打印当前节点，再递归调用右节点

代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        dfs(res,root);
        return res;
    }
    void dfs(List<Integer> res, TreeNode root) {
        if(root==null) {
            return;
        }
        dfs(res,root.left);
        res.add(root.val);
        dfs(res,root.right);
    }
}

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
        dfs(root)
        return res

145二叉树的后序遍历

思路

后序遍历：左、右、根，对于左子树、右子树来说，也是同样的遍历顺序。
重复子问题就：先遍历左子树、再遍历右子树、再取根节点。
终止条件:当前节点为空，没啥好遍历的。

代码

class Solution {
    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postOrder(self, root: TreeNode, res):
        if root == None:
            return
        self.postOrder(root.left, res)
        self.postOrder(root.right, res)
        res.append(root.val)
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.postOrder(root, res)
        return res