数据结构——二叉树

二叉树的前序遍历：（来着leetcodce 144）：

给你二叉树的根节点root ，返回它节点值的前序遍历。

示例1：

输入: root = [1,nu11,2,3]
输出: [1,3,2]

示例2：

输入: root = []
输出: []

示例3:

输入: root = [1]
输出: [1]

示例5:

输入: root = [1,2]
输出: [1,2]

代码：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root,res);
        return res;
    }

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

思路：利用递归的思路：定义 preorder(root) 表示当前遍历到 root 节点的答案。

按照定义，只要首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

二叉树的后序遍历：（来着leetcode 145）

给你一棵二叉树的根节点root，返回其节点值的后序遍历。

示例1：

输入: root = [A,nu1l,D,E]
输出: [E,D,A]

示例2：

root = []
输出: []

示例3：

输入: root = [1]
输出: [1]

代码：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root,res);
        return res;
    }

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

定义 postorder(root) 表示当前遍历到 root 节点的答案。

按照定义，我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树，然后递归调用 postorder(root->right) 来遍历 root 节点的右子树，最后将 root 节点的值加入答案即可，递归终止的条件为碰到空节点。

二叉树的中序遍历：（来自leetcode94）

示例1：

输入: root = [1,nu11,2,3]
输出: [1,3,2]

代码：

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

解析：中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，inoder(root)表示当前遍历的节点，之后递归调用inoder(root.left)来遍历root节点的左子树，将root节点的值加入list，inoder(root.right)来遍历root节点的右子树。递归到空节点为止。

相同的树：

给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。

如果两个树在结构.上相同，并且节点具有相同的值，则认为它们是相同的。

输入: p = [1,2,3]， q = [1,2,3]
输出: true

输入: p = [1,2], q = [1,null,2]
输出: false

代码：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }else if(p == null|| q == null){
            return false;
        }else if(p.val != q.val){
            return false;
        }else{
            return isSameTree(p.left,q.left) && isSameTree(p. right,q. right);
    }
}

解析：本题运用递归的方法，如果两个树都为空，则返回true。如果有其中一棵树为空，则返回false。如果两个树都不为空，则进行比较，如果值不相同就返回false，如果值相同就进行递归，比较左右两颗子树。