代码随想录训练营第十五天 ｜ 层序遍历 10，226.翻转二叉树 ，101.对称二叉树 2

今天是训练营的第十五天，继续二叉树方面的学习

 迭代法遍历：

前序：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        List<Integer> res = new ArrayList<>();

        if(root != null){
            s.push(root);
        }
        while(!s.isEmpty()){
            TreeNode temp = s.peek();
            if(temp!=null){
                s.pop();
                if(temp.right!=null){
                    s.push(temp.right);
                }
                if(temp.left!=null){
                    s.push(temp.left);
                }
                s.push(temp);
                s.push(null);
            }
            else{
                s.pop();
                res.add(s.pop().val);
                
            }
        }
        return res;
    }
}

中序：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();

        if(root!= null){
            st.push(root);
        }
        while(!st.isEmpty()){
            TreeNode temp = st.peek();
            if(temp!=null){
                st.pop();
                if(temp.right!=null){
                    st.push(temp.right);
                }
                st.push(temp);
                st.push(null);
                if(temp.left!=null){
                    st.push(temp.left);
                }

            }
            else{
                st.pop();
                res.add(st.pop().val);
            }
        }
        return res;
    }
}

后序：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        if(root != null){
            s.push(root);
        }

        while(!s.isEmpty()){
            TreeNode temp = s.peek();
            if(temp!=null){
                
                s.pop();
                s.push(temp);
                s.push(null);
                if(temp.right!=null){
                    s.push(temp.right);
                }
                
                
                if(temp.left !=null){
                    s.push(temp.left);
                }
                
                
                
                
            }
            else{
                s.pop();
                
                res.add(s.pop().val);
                
                
                
            }
        }
        return res;
    }
}

226. 反转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapTree(root);
        return root;
    }
    public void swapTree(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

用前序进行遍历

101. 对称二叉树

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

以中间节点为对称轴，反复对比每一个对称节点，有不一样的就返回false，直到全为空返回true；

树这个数据结构 我掌握的不太好