翻转二叉树（Java）

翻转二叉树

题目.png

//节点的数据结构
  Definition for a binary tree node.
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
   TreeNode(int x) { val = x; }
}

对于此题而言，我们使用深度优先算法来遍历二叉树。

1、深度优先算法是根据二叉树的路径进行遍历
2、广度优先算法是根据二叉树的层级进行遍历

如何针对二叉树的路径进行遍历呢？

• 使用递归，一直向下寻找，直到没有子节点。
• 只要将每个叶子节点都翻转一次，二叉树就完成了翻转。
• 每次递归，都将当前节点的子节点翻转，直至最末子节点，那么此时就完成二叉树的翻转。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        return dfs(root);
    }
    //深度优先
    public TreeNode dfs(TreeNode root){
        if(root == null) return root;
        //交换
        TreeNode transit = root.left;
        root.left = root.right;
        root.right = transit;
        if(root.left != null) root.left = dfs(root.left);
        if(root.right != null) root.right = dfs(root.right);
        return root;
    }
}