TREE

226. Invert Binary Tree

2017-07-12  本文已影响20人  DrunkPian0

翻转二叉树。Google的热身题。会写翻转二叉树你就比Max Howell强了。。

我的递归DFS代码:

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

另一种递归DFS代码:

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

        final TreeNode left = root.left,
                right = root.right;
        root.left = invertTree(right);
        root.right = invertTree(left);
        return root;
    }
}

另外这题用Stack和Queue都能解。
用Queue就是BFS。
Stack就是DFS! Stack执行过程跟递归DFS一样(DFS本身就是一层层的,神奇)。
详见:
https://leetcode.com/problems/invert-binary-tree/#/solutions

上一篇下一篇

猜你喜欢

热点阅读