【Leetcode】二叉树

编写二叉树

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }

题目编号

226 101

226. 翻转二叉树

解题思路

二叉树分为左右节点，首先考虑一个节点，将左右子节点交换，然后递归到左右子节点。结束条件是节点为null

代码

class Solution {
    public TreeNode invertTree(TreeNode root) {
        // 递归
        if(root == null) return null;

        // 创建交换的中间媒介
        TreeNode tmp = root.right;

        // 左右子树交换
        root.right = root.left;
        root.left = tmp;

        // 继续递归
        invertTree(root.right);
        invertTree(root.left);

        return root;
    }
}

101. 对称二叉树

解题思路

一开始我理解错了，以为就是一个判断根节点的左右子节点是否相等的问题。所以一开始的代码如下：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        while(root != null){
            if(root.left != root.right){
                return false;
            }else{
                isSymmetric(root.left);
                isSymmetric(root.right);
            }
        }
        return true;
    }
}

结果带入测试用例答案不对，才发现此题是判断右子节点的右节点和左子节点的左节点还有右子节点的左节点和左子节点的右节点是否相等。
这是一个典型递归问题,因为涉及到左子树的子节点和右子树的子节点，所以要另立一个函数isSub(TreeNode L, TreeNode R)来解决。
如果左右都为空，则返回true。如果只有其中一个为空或者两个值不相等，则返回false。其他情况则继续向下探索。

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true; // 根节点为空则返回true
        }else{
            return isSub(root.left, root.right); // 不为空则探索子节点
        }
    }
    public boolean isSub(TreeNode L, TreeNode R){
        if(L == null && R == null) return true; // 如果左右都为空，则返回true
        if(L == null || R == null || L.val != R.val){
            return false; // 如果只有其中一个为空或者两个值不相等，则返回false
        }else{
            return isSub(L.left, R.right) && isSub(L.right, R.left); // 其他情况则继续向下探索
        }
    }
}