树（简单）

二叉树的前序遍历

  • @递归

public static void preOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        preOrderRecur(head.left);
        System.out.print(head.val + " ");
        preOrderRecur(head.right);
    }

  • @迭代

public static void preOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

二叉树的中序遍历

  • @递归

public static void preOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.print(head.val + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

  • @迭代

public static void inOrderIteration(TreeNode head) {
            if (head == null) {
                return;
            }
            TreeNode cur = head;
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || cur != null) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode node = stack.pop();
                System.out.print(node.val + " ");
                if (node.right != null) {
                    cur = node.right;
                }
            }
        }

二叉树的后序遍历

  • @递归

public static void postOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        postOrderRecur(head.left);
        postOrderRecur(head.right);
        System.out.print(head.val + " ");
    }

  • @迭代

/*迭代写法，利用pre记录上一个访问过的结点，与当前结点比较，
    如果是当前结点的子节点，说明其左右结点均已访问，将当前结点出栈，
    更新pre记录的对象。 写法(3)：取巧的方法。该写法的访问顺序并不是后序遍历，
    而是利用先序遍历“根左右”的遍历顺序，
    将先序遍历顺序更改为“根右左”，反转结果List，得到结果顺序为“左右根”*/
    public List<Integer> postorderTraversal(TreeNode root) {//非递归写法
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();
            if((curr.left == null && curr.right == null) ||
                    (pre != null && (pre == curr.left || pre == curr.right))){
                //如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时，当前结点出栈
                res.add(curr.val);
                pre = curr;
                stack.pop();
            }else{
                if(curr.right != null) stack.push(curr.right); //先将右结点压栈
                if(curr.left != null) stack.push(curr.left);   //再将左结点入栈
            }
        }
        return res;
    }
/*
//方法(3)
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null) stack.push(node.left);//和传统先序遍历不一样，先将左结点入栈
            if(node.right != null) stack.push(node.right);//后将右结点入栈
            res.add(0,node.val);                        //逆序添加结点值
        }
        return res;
}

从上到下打印二叉树

public int[] levelOrder(TreeNode root) {
        Queue<TreeNode> q=new LinkedList<>();
        List<Integer> res=new ArrayList<>();
        if(root==null)
            return new int[]{};
        q.add(root);
        while(!q.isEmpty())
        {
            TreeNode temp=q.poll();
            res.add(temp.val);
            if(temp.left!=null)
                q.add(temp.left);
            if(temp.right!=null)
                q.add(temp.right);
        }
        int[] resf=new int[res.size()];
        for(int i=0;i<res.size();i++)
        {
            resf[i]=res.get(i);
        }
        return resf;
    }

从上到下打印二叉树II

 public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)
            return null;
        List<List<Integer>> res=new ArrayList();
        Queue<TreeNode> q=new LinkedList();
        q.add(root);
        while(!q.isEmpty())
        {
            List<Integer>tem=new ArrayList();
            for(int i=q.size();i>0;i--)
            {
                TreeNode no=q.poll();
                tem.add(no.val);
                if(no.left!=null) q.add(no.left);
                if(no.right!=null) q.add(no.right);

            }
            res.add(tem);
        }
        return res;
    }

二叉树的深度

  • @迭代

public int getTreeHeight(TreeNode root){
       if(null==root){
           return 0;
       }
       ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
       int height=0;
       queue.add(root);
       while(!queue.isEmpty()){
           int size=queue.size();
           for(int i=0;i<size;i++){
               TreeNode node=queue.removeFirst();
               if(null!=node.left){
                   queue.add(node.left);
               }
               if(null!=node.right){
                   queue.add(node.right);
               }
           }
           height++;
       }
       return height;
   }

  • @递归

 public int maxDepth1(TreeNode root)
    {
        if(root==null)
        {
            return 0;
        }
        int leftLen=maxDepth1(root.right);
        int rightLen=maxDepth1(root.left);
        return Math.max(leftLen,rightLen)+1;
    }
image.png

  • @递归一

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //根节点到p节点的路径
        List<TreeNode> path1 = new ArrayList<>();
        //根节点到q节点的路径
        List<TreeNode> path2 = new ArrayList<>();
        getPath(root,p,path1);
        getPath(root,q,path2);

        TreeNode result=null;
        int n = Math.min(path1.size(),path2.size());
        //保留最后一个相等的节点即为公共节点
        for(int i=0;i<n;i++){
            if(path1.get(i)==path2.get(i))
                result = path1.get(i);
        }
        return result;
    }
    //前序遍历搜索节点p或q
    void getPath(TreeNode root,TreeNode node,List<TreeNode> path){
        if(root==null)
            return ;
        path.add(root);
        if(root == node)
            return ;
        if(path.get(path.size()-1)!=node){
            getPath(root.left,node,path);
        }
        if(path.get(path.size()-1)!=node){
            getPath(root.right,node,path);
        }
        if(path.get(path.size()-1)!=node){
            path.remove(path.size()-1);
        }
    }

  • @递归二

/*
如果root是null，则说明我们已经找到最底了，返回null表示没找到
如果root与p相等或者与q相等，则返回root
如果左子树没找到，递归函数返回null，证明p和q同在root的右侧，
那么最终的公共祖先就是右子树找到的结点
如果右子树没找到，递归函数返回null，证明p和q同在root的左侧，
那么最终的公共祖先就是左子树找到的结点
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q)
            return root;
        TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode=lowestCommonAncestor(root.right,p,q);
        if(leftNode==null)
            return rightNode;
        if(rightNode==null)
            return leftNode;
        return root;
    }

  • @迭代一

 public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root.val==p.val||root.val==q.val)
        {
            return root;
        }
        HashMap<TreeNode, TreeNode> fathers = new HashMap<>();
        get_fathers1(fathers,root);
        ArrayList<TreeNode> p_path=get_path1(fathers,p);
        ArrayList<TreeNode> q_path =get_path1(fathers,q);
        return common_tail1(p_path,q_path);

    }
    public void get_fathers1(HashMap fathersMap,TreeNode root){
        Stack<TreeNode> fatherStack = new Stack<>();
        fatherStack.push(root);
        fathersMap.put(root,null);
        while (!fatherStack.isEmpty())
        {
            TreeNode temp=fatherStack.pop();
            if(temp.right!=null)
            {
                fatherStack.push(temp.right);
                fathersMap.put(temp.right,temp);
            }
            if(temp.left!=null)
            {
                fatherStack.push(temp.left);
                fathersMap.put(temp.left,temp);
            }
        }
    }
    public ArrayList<TreeNode> get_path1(HashMap<TreeNode,TreeNode> fathersMap,TreeNode target)
    {
        ArrayList<TreeNode> path = new ArrayList<>();
        path.add(target);
        while(fathersMap.get(target)!=null)
        {

            path.add(fathersMap.get(target));
            target=fathersMap.get(target);
        }
        return path;
    }
    public TreeNode common_tail1(ArrayList<TreeNode> p_path,ArrayList<TreeNode> q_path)
    {
        int p=p_path.size()-1,q=q_path.size()-1;
        while (p>=0&&q>=0&&p_path.get(p).val==q_path.get(q).val)
        {
            p--;
            q--;
        }
        return p_path.get(p+1);
    }

平衡二叉树

/*先序遍历*/
    public boolean isBalanced(TreeNode root) {
        if(root==null)
        {
            return true;
        }
        int lefthieght=gettreehieght(root.left);
        int rightHieght=gettreehieght(root.right);
        if(Math.abs(lefthieght-rightHieght)>1)
        {
            return false;
        }
        else {
            return isBalanced(root.left)&&isBalanced(root.right);
        }
    }
    public int gettreehieght( TreeNode root)
    {
        if(root==null)
        {
            return 0;
        }
        else
            return Math.max(gettreehieght(root.left),gettreehieght(root.right))+1;
    }

路径总和

int pathNumber=0;
    public int pathSum(TreeNode root, int sum) {
        if(root==null)
            return 0;
        Sum(root,sum);
        pathSum(root.left,sum);
        pathSum(root.right,sum);
        return pathNumber;
    }
    private void Sum(TreeNode root, int sum) {
        if(root==null)
            return;
        sum-=root.val;
        if(sum==0)
        {
            pathNumber++;
        }
        Sum(root.right,sum);
        Sum(root.left,sum);
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 【数据结构】树的简单分析总结（附js实现）
    本文会针对树这种数据结构，进行相关内容的阐述。其实本文应该算是一篇读书笔记。 文章首发于我的个人博客网站：http...
    前端西瓜哥阅读 2,143评论 0赞 2
  • 剑指offer之(树)
    树 写这个文章的目的是为了记录，好背。 树的遍历和树的深度是基础，很多题都是在遍历的基础上加些限制条件，下边题目的...
    桃之夭夭的简书阅读 283评论 0赞 0
  • 树的简单理解
    树的理解性定义 树的用处 树的实现和二叉树 树的遍历 1、树的理解性定义 树是分组、层次结构： 分组树由树根和其余...
    Valkyrie0阅读 954评论 0赞 2
  • 树的简单算法题
    二叉树插入 有序数组创建二叉树 遍历二叉树 algorithms/ 前序 根左右 中序 左根右 后序 左右根 递归...
    davidic阅读 437评论 0赞 0
  • 红黑树简单分析
    一、引入： 在理想情况下，二叉搜索树增删查改的时间复杂度为O(logN)。但是，在插入数据的时候，可能会导致树会倾...
    搞搞震_6d5a阅读 743评论 0赞 4