【1对】Symmetric Tree

2018-12-26  本文已影响4人  7ccc099f4608

https://leetcode.com/problems/symmetric-tree/

日期 是否一次通过 comment
2018-12-26 22:21 一次通过 sameTree的扩展
2018-12-27 14:24 看答案后通过 递归,理解不透;非递归,都为null时,漏掉continue
2019-01-13 16:06 一次通过 和sameTree共用一个模板
image.png

(来源: https://leetcode.com/problems/binary-tree-tilt/

递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        TreeNode node1 = root;
        TreeNode node2 = root;
        return dfs(node1, node2);
    }
    
    private boolean dfs(TreeNode node1, TreeNode node2) {
        if(node1 == null || node2 == null) {
            return node1 == node2;
        }
        
        if(node1.val == node2.val) {
            return dfs(node1.left, node2.right) && dfs(node1.right, node2.left);
        }
        
        return false;
    }
}

递归改进版

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        
        return dfs(root.left, root.right);
    }
    
    private boolean dfs(TreeNode node1, TreeNode node2) {
        if(node1 == null || node2 == null) {
            return node1 == node2;
        }
        
        if(node1.val != node2.val) {
            return false;
        }
        return dfs(node1.left, node2.right) && dfs(node1.right, node2.left);
    }
}

非递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        
        Stack<TreeNode[]> nodesS = new Stack<>();
        nodesS.push(new TreeNode[]{root.left, root.right});
        while(!nodesS.isEmpty()) {
            TreeNode[] treeNodes = nodesS.pop();
            if(treeNodes[0] == null || treeNodes[1] == null) {
                if(treeNodes[0] == null && treeNodes[1] == null) {
                    continue;
                }
                return false;
            }
            
            if(treeNodes[0].val != treeNodes[1].val) {
                return false;
            }
            nodesS.push(new TreeNode[]{treeNodes[0].left, treeNodes[1].right});
            nodesS.push(new TreeNode[]{treeNodes[0].right, treeNodes[1].left});
        }
        
        return true;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读