理论基础

二叉树的种类:满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树。

二叉树的存储方式链式存储线性存储

二叉树的遍历方式深度遍历前序中序后序),广度遍历(层次遍历)。

深度遍历力扣对应的三道题目

144. 二叉树的前序遍历

145. 二叉树的后序遍历

94. 二叉树的中序遍历


二叉递归遍历

递归前序遍历代码

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer&gt; res = new LinkedList<&gt;();
        if (root == null) {
            return res;
        }
        // 前序遍历结果特点:第一个是根节点的值,接着是左子树,最后是右子树
        res.add(root.val);
        res.addAll(preorderTraversal(root.left));
        res.addAll(preorderTraversal(root.right));
        return res;
    }
}

递归后序遍历代码

class Solution {
    public List<Integer&gt; postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        
        res.addAll(postorderTraversal(root.left));
        res.addAll(postorderTraversal(root.right));
        res.add(root.val);
        return res;
    }
}

递归中序遍历代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        
        res.addAll(inorderTraversal(root.left));
        res.add(root.val);
        res.addAll(inorderTraversal(root.right));
        return res;
    }
}

二叉树的迭代遍历

前序迭代遍历

思路:先将根节点放入栈中,然后从栈中弹出节点放进数组,将弹出节点的右孩子放入栈中,将弹出节点的左孩子放入栈中。直到栈空。(注意:要先将右孩子入栈,再将左孩子入栈,这样出栈顺序才是中、左、右,才符合前序遍历)。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 迭代法利用辅助操作
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ans.add(node.val); // 中
            if (node.right != null) {
                stack.push(node.right); // 右
            }
            if (node.left != null) {
                stack.push(node.left); // 左
            }
        }
        // 从栈中取出来就是左 右 ,顺序是中 左 右 符合前序
        return ans;
    }
}

后序迭代遍历

思路:根据前序遍历来修改得到,调换左右孩子入栈的顺序出栈顺序就是中、右、左,然后将数组反转,就得到左、右、中的遍历顺序,符合后序遍历。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // 迭代法利用栈辅助操作。
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ans.add(node.val); // 中
            if (node.left != null) {
                stack.push(node.left); // 左
            }
            if (node.right != null) {
                stack.push(node.right); // 右
            }
        }
        // 从栈中取出来顺序是 右 左 ,最后顺序为 中 右 左 
        // 反转数组后是 左 右 中,符合后序
        Collections.reverse(ans);
        return ans;
    }
}

中序迭代遍历

思路迭代法中,中序遍历的处理顺序和访问顺序是不一致的,需要借助指针来帮助遍历访问节点,栈用来处理节点。先将指针指向根节点,只要指针或栈不为空,就进行遍历操作,如果指针为空当前元素入栈,指针指向左孩子,如果指针为空,指针指向栈中的出栈元素,将元素值存入数组中,然后指针指向当前元素的右孩子。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 迭代法,用栈记录遍历过的元素
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                current = stack.pop();
                ans.add(current.val);
                current = current.right;
            }
        }
        return ans;
    }
}

二叉树的统一遍历

思路:递归遍历无法统一写法原因无法同时解决访问节点(遍历节点)和处理节点(将元素放进结果集)不一致的情况解决方法是将访问的节点放入栈中,把要处理的节点也放入栈中,但紧接着要放入一个空指针作为标记。(注意:Java中Stack可以push(null)而Deque可以

前序代码

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                st.pop(); 
                // 添加右节点(空节点不入栈)
                if (node.right != null) st.push(node.right); 
                // 添加左节点(空节点不入栈)
                if (node.left != null) st.push(node.left);
                // 添加中节点
                st.push(node);
                // 中节点访问过,但是还没有处理加入空节点做为标记
                st.push(null);
                
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入结果
            }
        }
        return result;
    }
}

中序代码

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                st.pop(); 
                // 添加右节点(空节点不入栈)
                if (node.right != null) st.push(node.right); 
                // 添加中节点
                st.push(node);
                // 中节点访问过,但是还没有处理,加入空节点做为标记
                st.push(null);
                // 添加左节点(空节点不入栈)
                if (node.left != null) st.push(node.left);    
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入结果
            }
        }
        return result;
    }
}

后序代码

class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                st.pop(); 
                // 添加中节点
                st.push(node); 
                // 中节点访问过,但是还没有处理,加入空节点做为标记
                st.push(null); 
                // 添加右节点(空节点不入栈)
                if (node.right != null) st.push(node.right);
                // 添加左节点(空节点不入栈)
                if (node.left != null) st.push(node.left);
                               
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入结果
            }
        }
        return result;
   }
}

原文地址:https://blog.csdn.net/qq_41541801/article/details/134747025

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_33152.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注