二叉树

二叉树最重要的是先知道当前root的节点需要做什么，然后再根据函数定义进行递归调用子节点，如何提炼出叶子结点要做的事情也正是二叉树的难点所在。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

排序

前序遍历：中–>左–>右
中序遍历：左–>中–>右
后续遍历：左–>右–>中

94. 二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

// 递归法
class Solution {
	
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
   // 前序遍历
    public  void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        inorder(root.left, result);
        inorder(root.right, result);
    }
    // 中序遍历
    public  void inorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
    // 后序遍历
    public  void postorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorder(root.left, result);
        inorder(root.right, result);
        result.add(root.val);
    }
     
}

101.判断二叉树是否对称

https://leetcode.cn/problems/symmetric-tree/
理思路
1、如果二叉树根节点为空，那么为对称二叉树
2、如果左子树 == 右子树，那么为对称二叉树
3、如何判断左子树 == 右子树？左子树的左子节点右子树的右子节点，左子树的右子节点右子树的左子节点

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        return cmp(root.left, root.right);
    }

    public boolean cmp(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        return node1.val==node2.val && cmp(node1.left, node2.right) && cmp(node1.right, node2.left);
    }
}

104. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

当前节点要做的事情：返回当前节点的最大深度，然后+1（当前节点）

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}

226. 翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/
当前节点要做的事情：左右子树交换

Class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode left = root.left;
        root.left = root.right;
        root.right = left;

        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}

543. 二叉树的直径

https://leetcode.cn/problems/diameter-of-binary-tree/
当前节点要做的事情：左右子树的高度和的最大值

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        setDepth(root);
        return max;
    }

    int max = 0;

    public int setDepth(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int left = setDepth(treeNode.left);
        int right = setDepth(treeNode.right);
        if (right + left > max) {
            max = left + right;
        }
        return Math.max(left, right) + 1;
    }
}

617. 合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/
当前节点要做的事情：判断节点是否为null，全为空，部分为空，都不为空

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}