面试题28. 对称的二叉树

川长思鸟来 2023-02-18 11:50 8阅读 0赞

# 题目来源 #

[面试题28. 对称的二叉树][28.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 递归 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null){
        
                return true;
            }
            
            return helper(root.left, root.right);
        }
        
        private boolean  helper(TreeNode left, TreeNode right){
        
            if (left == null && right == null){
        
                return true;
            }
            
            if (left == null ){
        
                return false; 
            }
            
            if (right == null){
        
                return false;
            }
            
            if (right.val != left.val){
        
                return false;
            }
            
            return helper(left.left, right.right) && helper(left.right, right.left);
        }
    }

![在这里插入图片描述][20200617161624529.png]

## 辅助栈 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null){
        
                return true;
            }
    
            
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root.right);
            stack.push(root.left);
            while (!stack.empty()){
        
                TreeNode left = stack.pop();
                TreeNode right = stack.pop();
    
                if (left == null && right == null){
        
                    continue;
                }
                
                if (left == null){
        
                    return false;
                }
                
                if (right == null){
        
                    return false;
                }
    
                if (left.val != right.val){
        
                    return false;
                }
                
                stack.push(left.left);
                stack.push(right.right);
    
                stack.push(left.right);
                stack.push(right.left);
            }
    
            return true;
        }
    }

![在这里插入图片描述][20200617161302993.png]

[28.]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617161707539.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200617161624529.png]: https://img-blog.csdnimg.cn/20200617161624529.png
[20200617161302993.png]: https://img-blog.csdnimg.cn/20200617161302993.png