7 分钟 读完 (大约 1040 个字)

二叉树算法

- 二叉树的打印，前中后序遍历, 递归&非递归#

非递归先序遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> preOrder(BinaryTree node) {

    List<Integer> list=new ArrayList<Integer>();
    if(node==null) return list;
    Stack<BinaryTree> stack= new Stack<BinaryTree>();
    while(node!=null || !stack.empty()) {
        if(node!=null){
            list.add(node.val);
            stack.push(node);
            node=node.left;
        } else {
            node=stack.pop();
            node=node.right;
        }
   } 
   return list;
}

非递归中序遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> inOrder(BinaryTree node) {

    List<Integer> list=new ArrayList<Integer>();
    if(node==null) return list;
    Stack<BinaryTree> stack= new Stack<BinaryTree>();
    while(node!=null || !stack.empty()) {
        if(node!=null){
            stack.push(node);
            node=node.left;
        } else {
            node=stack.pop();
            list.add(node.val);
            node=node.right;
        }
   } 
   return list;
}

非递归后序遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postOrder(BinaryTree node) {

    List<Integer> list=new ArrayList<Integer>();
    if(node==null) return list;
    Stack<BinaryTree> stack= new Stack<BinaryTree>();
    while(node!=null || !stack.empty()) {
        if(node!=null){
            list.add(0, node.val);
            stack.push(node);
            node=node.right;
        } else {
            node=stack.pop();
            node=node.left;
        }
   } 
   return list;
}

022-从上往下打印二叉树 *#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            result.add(temp.val);
            if(temp.left != null) queue.offer(temp.left);
            if(temp.right != null) queue.offer(temp.right);
        }
        return result;
    }
}

060-把二叉树打印成多行#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    if(pRoot == null){
        return list;
    }
    Queue<TreeNode> queue = new LinkedList();
    //根节点入队列
    queue.offer(pRoot);
    //当队列不是空
    while(!queue.isEmpty()){
        //放里面，记录当前节点个数
        int size  = queue.size();
        ArrayList<Integer> temp = new ArrayList();
        //遍历一次是一层
        for(int i=0;i<size;i++){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            temp.add(node.val);
        }
        list.add(temp);
    }
    return list;
}

059-按之字形顺序打印二叉树 *#

按行打印的部分，按奇偶来改变头插尾插

023-二叉搜索树的后序遍历序列 *#

同非递归二叉树的后序遍历， 思路: 先序是 abc, acb, 的反转 bca即需要的后序遍历。使用栈， 与先序写法差不多，只是先push right, 再left, list.add用头插.

024-二叉树中和为某一值的路径#

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    find(root, target, 0, new ArrayList<Integer>(), result);
    return result;
}

private void find(TreeNode node, int target, int sum, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result) {

    sum += node.val;
    path.add(node.val);

    if (node.left == null && node.right == null && sum == target) {
        result.add(new ArrayList<>(path));
        path.remove(path.size() - 1);
        return;
    }
    
    if (node.left != null) {
        find(node.left, target, sum, path, result);
    }
    if (node.right != null) {
        find(node.right, target, sum, path, result);
    }
    path.remove(path.size() - 1);
}

038-二叉树的深度#

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int TreeDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    if (root.left == null && root.right == null) {
        return 1;
    }
    
    int leftDepth = TreeDepth(root.left);
    int rightDepth = TreeDepth(root.right);
    
    return 1 + Integer.max(leftDepth, rightDepth);
}

二叉树层次遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();
    if (root == null) return levels;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    int level = 0;
    while ( !queue.isEmpty() ) {
      // start the current level
      levels.add(new ArrayList<Integer>());

      // number of elements in the current level
      int level_length = queue.size();
      for(int i = 0; i < level_length; ++i) {
        TreeNode node = queue.remove();

        // fulfill the current level
        levels.get(level).add(node.val);

        // add child nodes of the current level
        // in the queue for the next level
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
      }
      // go to next level
      level++;
    }
    return levels;
}

114. 二叉树展开为链表#

直接展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void flatten(TreeNode root) {
    TreeNode node = root;
    while (node != null) {
        
        // 
        if (node.left == null) {
            node = node.right;
            continue;
        }

        // 找到左分支的最右节点
        TreeNode pre = node.left;
        while (pre.right != null) {
            pre = pre.right;
        }        

        // pre 替换node 右分支的位置
        pre.right = node.right;
        node.right = node.left;
        node.left = null;
        node = node.right;
    }
}

236. 二叉树的最近公共祖先#

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Stack<TreeNode> stack = new Stack();
    Map<TreeNode, TreeNode> son2ParentMap = new HashMap();
    stack.push(root);
    son2ParentMap.put(root, null);
    while (!son2ParentMap.containsKey(p) || !son2ParentMap.containsKey(q)) {
        TreeNode node = stack.pop();
        if (node.left != null) {
            son2ParentMap.put(node.left, node);
            stack.push(node.left);
        }
        if (node.right != null) {
            son2ParentMap.put(node.right, node);
            stack.push(node.right);
        }
    }
    Set<TreeNode> sets = new HashSet();
    while (p != null) {
        sets.add(p);
        p = son2ParentMap.get(p);
    }
    while (!sets.contains(q)) {
        q = son2ParentMap.get(q);
    }
    return q;
}

105. 从前序与中序遍历序列构造二叉树#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
}

private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
    // preorder 为空，直接返回 null
    if (p_start == p_end) {
        return null;
    }
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    //在中序遍历中找到根节点的位置
    int i_root_index = 0;
    for (int i = i_start; i < i_end; i++) {
        if (root_val == inorder[i]) {
            i_root_index = i;
            break;
        }
    }
    int leftNum = i_root_index - i_start;
    //递归的构造左子树
    root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index);
    //递归的构造右子树
    root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end);
    return root;
}

101. 对称二叉树#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

101. 平衡二叉树#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

喜欢这篇文章？打赏一下作者吧

栈&队列算法
hashmap算法
关注我

链接

分类

标签云

List concurrenthashmap design framework git hadoop hashmap innodb java jvm kafka maven mybatis mysql netty network pcursor redis rss spring springboot storm tair vim zookeeper 并发 旅游 机器学习 生活 索引 线上问题 英语 设计模式 读书笔记 锁 面经

最新文章

归档

标签

List 1
concurrenthashmap 1
design 8
framework 1
git 1
hadoop 2
hashmap 9
innodb 2
java 15
jvm 3
kafka 1
maven 1
mybatis 3
mysql 11
netty 3
network 2
pcursor 1
redis 3
rss 1
spring 1
springboot 5
storm 1
tair 1
vim 1
zookeeper 2
并发 4
旅游 3
机器学习 1
生活 2
索引 2
线上问题 1
英语 1
设计模式 1
读书笔记 1
锁 1
面经 1

最新文章

归档

标签

List 1
concurrenthashmap 1
design 8
framework 1
git 1
hadoop 2
hashmap 9
innodb 2
java 15
jvm 3
kafka 1
maven 1
mybatis 3
mysql 11
netty 3
network 2
pcursor 1
redis 3
rss 1
spring 1
springboot 5
storm 1
tair 1
vim 1
zookeeper 2
并发 4
旅游 3
机器学习 1
生活 2
索引 2
线上问题 1
英语 1
设计模式 1
读书笔记 1
锁 1
面经 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×